Vizualizare sursă pentru „4203 - Number of Points”

În planul <code>xOy</code> se găsesc <code>n</code> puncte de coordonate numere naturale nenule, nu neapărat aflate pe poziții distincte.

= Cerința =
Pentru fiecare punct din plan de coordonate <code>(x, y)</code> trebuie să spuneți câte alte puncte au coordonatele <code>(p, q)</code> cu proprietatea că <code>1 ≤ p < x</code> și <code>1 ≤ q ≤ y</code> (atenție, <code>p</code> este strict mai mic decât <code>x</code>, iar <code>q</code> este mai mic sau egal cu <code>y</code>).

= Date de intrare =
Fișierul de intrare <code>numberofpointsIN.txt</code> conține pe prima linie, separate prin câte un spațiu, numerele <code>n</code>, <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code>, <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>, unde <code>n</code> este numărul de puncte din plan, <code>(x1, y1)</code> sunt coordonatele primului punct din plan, iar <code>(x2, y2)</code> sunt coordonatele celui de-al doilea punct. Coordonatele restului punctelor se generează după formulele:

* <code>xi</code> <code>= (xi-2</code> <code>* A + xi-1</code> <code>* B + C) % D + 1</code>, pentru orice <code>i=3..n</code>
* <code>yi</code> <code>= (yi-2</code> <code>* A + yi-1</code> <code>* B + C) % D + 1</code>, pentru orice <code>i=3..n</code>

= Date de ieșire =
Fișierul de ieșire <code>numberofpointsOUT.txt</code> va conține exact <code>n</code> linii, pe linia <code>i</code> (cu <code>i = 1..n</code>) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât <code>xi</code> și ordonata mai mică sau egală decât <code>yi</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 200.000</code>
* <code>1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000</code>

= Exemplul 1: =
<code>numberofpointsIN.txt</code>
 7 19 17 11 23 4 5 7 2
<code>numberofpointsOUT.txt</code>
 1
 1
 2
 2
 4
 0
 5

=== Explicații ===
Cele șapte puncte generate au coordonatele: <code>(4, 5)</code>, <code>(7, 2)</code>, <code>(23, 3)</code>, <code>(7, 9)</code>, <code>(16, 15)</code>, <code>(3, 1)</code> și <code>(22, 15)</code>. Primul punct, de coordonate <code>(4, 5)</code> are un singur punct care îndeplinește cerințele, anume cel de coordonate <code>(3, 1)</code>. Al cincilea punct, de coordonate <code>(16, 15)</code> are <code>4</code> puncte care îndeplinesc condițiile, anume <code>(4, 5)</code>, <code>(7, 2)</code>, <code>(7, 9)</code> și <code>(3, 1)</code>.

== Exemplul 2: ==
<code>numberofpointsIN.txt</code>
 0 19 17 11 23 4 5 7 2
<code>numberofpointsOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

def read_input(file):
    with open(file, "r") as f:
        data = f.read().split()
    return list(map(int, data))

def write_output(file, data):
    with open(file, "w") as f:
        f.write(data)

class Punct:
    def __init__(self, x, y, ind):
        self.x = x
        self.y = y
        self.ind = ind

def csort(a, b):
    if a.x != b.x:
        return a.x - b.x
    return a.y - b.y

def update(tree, node, st, dr, poz):
    if st == dr:
        tree[node] += 1
        return
    mid = (st + dr) // 2
    if poz <= mid:
        update(tree, 2 * node, st, mid, poz)
    else:
        update(tree, 2 * node + 1, mid + 1, dr, poz)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

def query(tree, node, st, dr, val):
    if dr <= val:
        return tree[node]
    if st == dr:
        return 0
    mid = (st + dr) // 2
    q1 = query(tree, 2 * node, st, mid, val)
    q2 = 0
    if val > mid:
        q2 = query(tree, 2 * node + 1, mid + 1, dr, val)
    return q1 + q2

def verifica_restrictii(n, A, B, C, D):
    if not (1 <= n <= 200000 and 1 <= A <= 1000000 and 1 <= B <= 1000000 and 1 <= C <= 1000000 and 1 <= D <= 1000000):
        return False
    return True

def main():
    data = read_input("numberofpointsIN.txt")
    n, A, B, C, D = data[0], data[1], data[2], data[3], data[4]
    
    if not verifica_restrictii(n, A, B, C, D):
        write_output("numberofpointsOUT.txt", "Datele nu corespund restrictiilor impuse")
        return

    v = []
    idx = 5
    for i in range(1, n + 1):
        if i <= 2:
            x, y = data[idx], data[idx + 1]
            idx += 2
        else:
            x = (v[i - 3].x * A + v[i - 2].x * B + C) % D + 1
            y = (v[i - 3].y * A + v[i - 2].y * B + C) % D + 1
        v.append(Punct(x, y, i))
    
    v.sort(key=lambda p: (p.x, p.y))
    
    CMAX = 1000000
    tree = [0] * (4 * CMAX + 1)
    ans = [0] * (n + 1)
    same_x = [0] * (CMAX + 1)
    
    for i in range(n):
        ans[v[i].ind] = query(tree, 1, 1, CMAX, v[i].y) - same_x[v[i].x]
        same_x[v[i].x] += 1
        update(tree, 1, 1, CMAX, v[i].y)
    
    output = "\n".join(map(str, ans[1:]))
    write_output("numberofpointsOUT.txt", output)

if __name__ == "__main__":
    main()

</syntaxhighlight>