| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 730838 | josanneo22 | 팀들 (IOI15_teams) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//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))
*/