| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 730838 | josanneo22 | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//sort K by ascending order of team size, sort A and B by A[i]
/* subtask 1&2:
assign greedily for each k[i]
find smallest a[i] such that k[i]>=a[i]
after that just keep assigning until the end
then we check if any k[i] fails to find a pair
in this case we can use vector then erase:
O(nlog n) should pass
subtask 3&4:
in order to speed up the program:
infeasible to reset every time: O(n*q)
a data strucutre that allows:
find unused a[i] in a better way
AND reset all to be unused
[shouting loudly]USE A SEGMENT TREE
find index i first:
then how to find closest j(j>=i) such that it is unused
binary search on a segment tree on range[i,n] log n
we can use bitwise AND segment tree
update(j) to be 1(used)
since we need to reset everything to be unused:
we also need to have a range update to all unused
so change to a LAZY SEGTREE
update and reset in O(log n) time
binary search on segment tree: O(qlog n* log n)
so sort+segtree operations=O(nlog n+ qlog^2 n) time
which should pass through subtask 3 and 4
subtask 5:
i was thinking of mo's algorithm and somehow do it in O(q*sqrt(n))
*/