| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi all,
join us on the fifth round which will be held on Saturday, February 8th at 14:00 UTC.
If you are not familiar with the COCI contest format, we encourage you to read the announcement for the new season. You can also find the problems from the previous rounds here.
Feel free to discuss the problems in the comment section after the contest ends.
See you on Saturday!
Didn't happened, sad :(
How do you solve problem 'Matching' faster than $$$N^2$$$?
Build a graph of adjacent guys, deal with degree 1 vertices, and then check that all cycles are even.
After that, quadratic solution is just two-sat, because for each cycle there are only two possible shifts.
To optimize this solution, you can build a two-sat graph more efficiently using sweep line and persistent segment tree, similar to this problem: link
2sat is more like dsu in this case, because any 2 intersecting segments just means that all involved vertices should have their segments in the same direction
I don't think this is true. There are cases where two points A and B are allowed to have A vertical and B horizontal, but not A horizontal and B vertical.
Here's a case that should illustrate this:
I think I was not clear. My solution is as follows — consider all intersecting pairs. I postulate that all 4 involved vertices should have the same orientation. Also any 2 vertices with same coordinate should have the same orientation. So now we have some sets of vertices that all have same orientation. Now for some vertices we know that they should have vertical segment (because no other vertex have same y) or we know that it should have horizontal segment. If some set have vertices of both this types, answer is NE. If only one — we should direct all segments in the set in corresponding direction. If all vertices in the set can be connected either way — we can arbitrary select which way we will connect
In other words, all conditions in the problem lead to 3 kind of equivalences:
This post could be helpful.
There is a relatively simple way of building the graph.
For a segment S, let C[s] denote it's component.
Do a sweep from left to right and maintain a segment tree for y-coordinates:
a horizontal segment can become active/inactive, mark that position in segment tree with C[s]
merge a vertical segment with all horizontal segments which are active and intersect it
For 2, query the minimum and maximum in the interval and while they are different merge one of them with the vertical segment. The merges can be done small-to-large. The total complexity is O(N log^2 N) because when merging we also update the segment tree.
Btw I used sqrt decomposition, and it passed after fixing stupid bug
You can solve all the problems here: https://oj.uz/problems/source/446