4203 - Number of Points

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

Cerința

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

Date de intrare

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

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

Date de ieșire

Fișierul de ieșire numberofpointsOUT.txt va conține exact n linii, pe linia i (cu i = 1..n) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât xi și ordonata mai mică sau egală decât yi.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• 1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000

Exemplul 1:

numberofpointsIN.txt

7 19 17 11 23 4 5 7 2

numberofpointsOUT.txt

1
1
2
2
4
0
5

Explicații

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

Exemplul 2:

numberofpointsIN.txt

0 19 17 11 23 4 5 7 2

numberofpointsOUT.txt

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>