PAST2N
https://gyazo.com/e061127462d65fbc91305c7902b100a7
PAST2N
Thoughts.
Find 5,000 squares that contain it for a point and add up the cost.
However, linear orders will not make it in time.
what to do about it
If it were one-dimensional, we would record the points of variation of the cumulative sum and perform a binary search, but this time it is two-dimensional.
Is it the 2-D Imosu method?
It seems impossible to do it in two dimensions since the coordinates are 10^5 even after compressing the coordinates.
Official Explanation
A new thought.
If you process N squares per query, no matter how fast the individual process is, you'll never make it in time.
Include the boundaries of the intervals, so they are mixed and sorted by (y, x)
https://gyazo.com/2fd0b0bd0c92f206061c4b4ef25c4fec
mounting
I noticed it when I tried to make a segmented tree.
When RangeAdd and Read overlap at the same coordinates, the starting RangeAdd must be processed before Read because of the "square corners are also inside the square" specification.
Conversely, the closing RangeAdd must be processed later.
Let's shift the coordinates by 0.5.
Sample 1 came through, but negative values came up in sample 2.
→The mistake was accessing the segment tree with the original coordinates, even though the coordinates were compressed.
AC
code:python
def solve(N, Q, SS, QS):
xs = []
for x, _, width, _ in SS:
xs.append(x)
xs.append(x + width)
for x, _ in QS:
xs.append(x)
xs.sort()
x2i = {}
for i, x in enumerate(xs):
i2x = xs
commands = []
for x, y, width, cost in SS:
commands.append((
y, start - 0.5,
"add",
start, end, cost
))
commands.append((
y + width, end + 0.5,
"add",
start, end, -cost
))
for x, y in QS:
commands.append((
"read",
None, None, None
))
commands.sort()
result = {}
# segtree
from operator import add
set_width(len(x2i) + 10)
for y, x, typ, start, end, cost in commands:
if typ == "add":
# range add as two point_add
point_set(table, start, get_value(table, start) + cost, add)
point_set(table, end + 1, get_value(table, end + 1) - cost, add)
else:
# point read as range sum
v = range_reduce(table, 0, x + 1, add, 0)
# print answer
for q in QS:
---
This page is auto-translated from /nishio/PAST2N. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.