Здравствуй, Codeforces!
5 августа 2015 года в 19:00 Мск состоится Codeforces Round #Pi для участников второго дивизиона. Участники первого дивизиона традиционно могут поучаствовать вне конкурса.
Это мой первый раунд на Codeforces. Надеюсь, что задачи вам понравятся и это даст мне стимул для подготовки новых раундов! Желаю всем быстрых Accepted и успешных взломов!
Хочу поблагодарить Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces и за помощь в придумывании задач, Максима Ахмедова (Zlobober) за помощь в подготовке соревнования, Марию Белову (Delinur) за перевод условий на английский, а также моих друзей Данила Сагунова (danilka.pro) и Виталия Кудасова (kuviman) за прорешивание задач.
Участникам будет предложено 6 задач и два с половиной часа на их решение. Разбалловка будет объявлена ближе к началу раунда.
UPD: Разбалловка: 500-1000-1500-2000-2500-2500.
UPD: Разбор
I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?
Maybe because it's round 314.
As a remainder PI = 3.1415...
Oh, it seems so :) I thought that round #314 will be held after Pi-round, but I was wrong.
P.S. Thanks for clarifying. Perhaps, I would not participate in this round because Pi-round sounds like a Math-round. And I'm weak at math :P
So, next PI round will be at 3141 th contest ... about 3000 rounds later :v :P
Looking forward to participate in that Round :)
Well, that would be more than 50 years from now. So, I don't want to miss today's Pi round. Let's hope that, we can see our grandchildren participating in a CF Pi-round :P
Too bad ;( We lost "Round #e" (271). I love "e" more than "pi".
Hopefully there will be interesting and original math problems!
What is the point of hoping for something like this; this is not IMO. Instead, you should be hoping for an interesting and varied problem-set — one consisting of other things as well.
Because it is Pi round, hope for comp geo :O
nezt PI Round #3141 ?
According to this logic, first Pi round was 3, but was it?
Another round is 31, but was it?
And round 1,4,9,16,... should be perfect square rounds, but 1 should also be square root round, but were they?
In that logic every round should be named integer round -_-
Hello! Should I pronounce your name as Pi-kachu?
ლ(ಠ益ಠლ)
I like this picture very much but what does it mean here??????????????? :|
this contest prepared by P1kachu :)
Oh I realized :( Thank you for your answer :) Nice picture ;)
welcome~ hope you have a good contest!
so cute ^_^
"В раунде ожидается 2*Pi задач. Так как это число меньше семи, то проведение раунда для обоих дивизионов невозможно, only div 2. Но так как это число больше пяти, то на решение задач будет дано два с половиной часа."
В америке в одно из штатов число Pi равно четырем. НИЗОЩИТАН!
.
I think I'll skip this one and wait for Codeforces Round #Tau
Is it a rating round？
of course
Ok. Come on!
Nice try Internet Explorer(or Edge)... Very nice try...
Speaking of internet explorer reminds me this pic:
Codeforces Round #FF also instead #255.
Maybe there will be a problem about circles ? :-)
Maybe there will be a problem about circles ? :-)
Why are you so diao?
Oh , xiaoxin juju appears upstairs！
baba will not like you TUT
oh~xiaoxin juju
i do think geometry is your dish.
You were wrong :D
Oh~ it seems that the writer missed a good opportunity :P
So this contest will be all about math problems? (#Pi)
It will be crazy, I guess.
I think that this round shuld be irracionally long. Lets say 3h 8m 30s or 3.14h :)
Здесь: Участникам будет предложено 6 задач и два с половиной часа на их решение.
Оповещение на почте: Продолжительность соревнования — 2 часа.
Где правда?
Тут: http://mirror.codeforces.com/contests время тоже два с половиной. Видимо, на почту оповещение неправильное сформировалось.
i'm thinking what will a Codeforces Round #i be like... i'd be imaginary for sure :D
"Wish you quick Accepted verdicts and successful hacks." — interesting combination. To hack successfully, I need to lock a problem. Then someone hacks me (according to your wishes) and I can't correct my solution because I've locked it before. Very sad scenario.
Anyway, have fun everybody :)
paradoxical :p
What bothers me usually is when authors wish high ratings for all of the participants :-/
How does Tourist get rating rise?
Well, I assume he wins contests.
You get rating rise when you perform better than your expected position in a contest. Tourist's expected position=1. He can't be better than 1. Yet, he gets rating rise. Am I missing something?
I really do not know how the rating works, but I guess that expected position doesn't have to be an integer. He'd get precisely expected position 1 if he were to compete alone, any participant added should change his expected position a bit, but in the end it probably stays in the interval [1;2], so getting 1 is the only way to score better than his expected position :)
So lock in the last 5 minutes, and spend 2hr 25 minutes before that making sure your answer is correct :)
You solved C in 3 minutes!!! What is this sorcery?
totsamyzed had A after 2 minutes (1:56). I was ~80 seconds slower in task with roughly the same amount of code needed. It doesn't look like sorcery.
Like you didn't even have to read the question, you just started typing #JustDiv1CoderThings
why 2:30 ??????
why 2:30 ???
Six problems I guess :p
ВСЕМ УДАЧИ НА СЕГОДНЯШНИМ СОРЕВНОВАНИИ!!
ПУСТЬ У ВАС БУДЕТ БОЛЬШОЙ РЕЙТИНГ И ВСЕ ХОРОШО!!!
Не думаю что на CF у всех проблемы со зрением.
ОПЯТЬ ТЫ))))) На кодфорцезе у всех проблемы с логикой а не зрением))))) а большими буквами потому что искрени от всей души!!!!!
Да, после слова "искрени" глаза выпадывают, проблемы со зрением появляются, и большие буквы становятся полезными.
Поэтому ты и красный :)))) В задачках шаришь а в нормальном человечиском общении неочень((((
Вызов принят.
)))
ФУУУУУУУУУ!!!! СПИСЫВАЛЬЩИК!!!!!! http://mirror.codeforces.com/contest/567/submission/12374586
ПОЗОР ТЕБЕ!!!!!!!!!!!!
ТЫ ЖАЛОК!!!!!!
сегодняшнЕм
Какая разница кто как пишит???
Грамотное письмо радует глаз, делает общение намного интереснее, улучшает мнение о собеседнике
лучше рейтинг себе подними а не чем на грамотность внимание обращай!!!!
СПАСИБО! И ТЕБЕ УДАЧИ MAXIMAN!!!
Неужели на CF появился более упоротый человек, чем я 6 лет назад?
Ты был зарегистрирован 5 лет назад. Судя по твоему комментарию, ты должен быть в CF минимум 6 лет.
Вообще-то, нет. То, что я был упорот, не означает, что я был зарегистрирован на КФ. Не все упоротые регистрируются тут, знаете ли. Однако, действительно, спасибо за исправление)
So i guess in each of the problems today we have to be introduced with the person "Mr. PI" :D :D :D
when you are wishing for some body successful hacks you are wishing for some body else unsuccessful
submits!!! i don't think it's a good wish!
thanks ;)
2.5 hour = 6 problems? So I guess P1kachu prepare a nice problem F for us to solve...
define in_round_#pi ++
int RP;
int main(){ while(RP)RPin_round_#pi; return 0; //By the way,thanks to writer }
Round #404 will be declared as round #Error or round #NotFound
Nice idea !!
numbered rounds of Fibonacci numbers: round #Fibonacci
P.S. Next Fibonacci round is 377 *
now I found out first comment in blog create other comment first comment: "I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?" other comments also are about name of contests
just kek
That proud moment when a blue coder prepares a CF round :D
Hats off !!! keep it up :D
This is the first contest i join ever on codeforces :)
OK. Good Luck :)
Автокомментарий: текст был обновлен пользователем Zlobober (предыдущая версия, новая версия, сравнить).
Максииим, привет!
It has been a long time since the last Div2 contest.. It's obvious that the number of registrants is very large this time and people are eager for such an event.. Let's enjoy
I'll be Grey in no time
So since there are 6k+ participants, on a scale from Google.com to contest.Bayan.ir, how down is Codeforces.com going to be ?
6278 people registered which is more than 6274 people registered for good bye 2014
out of 6278 registrants 935 people are unrated
The first round was written by Expert user that I have ever participated!
What on earth is pretest 19 in Problem E?
I guess you're not finding the bridges correctly. I got WA 19 because of a caveat in my solution, I only check for edges that definitely are on the shortest path ONLY from the start and the end, but there could actually be bridges in the middle of the path too. An example edge formation , start = 1 , end = 8 : 1 2 1 3 2 4 3 4 4 5 5 6 5 7 7 8 6 8
The edge 4 5 is definitely on the shortest path since it is a bridge in the shortest path graph. Hope it helps .
No, I think I took care of that. Oh well, will wait for the editorial for E.
Problem E with modulo based hacking was pretty funny.
I had a generator that generates a input for any mod. Some guy from my room sent his solution in the last moment to make sure that I can not hack him. :)
Is there a solution without modulo calculations?
What is a solution with modulo calculations?
@ikbal can you show how you made the generator?
Also I used doubles to calculate number of paths. Paths can be at most 10^500 which fits in a double.
With modulo calculations, you just mod this number continuously.
We build DAG where there is a directed edge (u,v) if there is an edge (u,v) in graph and dest[s,u]+dest[u,v]+dest[v,t]==dest[s,t]. Then we say that edge (u,v) is a bridge if number of ways (s,u)*(v,t)=(s,t). But this values are large, so I took them by modulo
Instead of counting number of ways you can change this DAG into undirected graph (all edges become bidirectional) and just find all bridges in this graph.
Can you please explain why this is correct ?
I got a WA using an undirected graph. Can you explain the proof of this?
Yes, there is. And not only one.
1) You can find all edges that can be in shortest path and then find bridges in this graph.
2) Find all edges that can be in shortest path. Then realize that we are on this edge in fixed interval of time. Edge is in all shortest paths if its interval doesn't intersect with other intervals. (It's my solution, you can read it).
Was my solution also hacked because of modulo? It would be quite strange since I used both overflow hash & modulo. I even changed modulo after getting hacked, but still got WA (on your hack).
Just create two paths one with 10^9+7 and one with 2^64 ways. If we merge them together from their ends by an edge new long path would have (10^9+7 * 2^64) ways.
What sense not to be hacked if solution is wrong?
Because usually it's impossible for problem setter to create tests against every modulo.
I'm wondering if his code gets accepted after all. :/
Yes:D
12374662
P.S. Glad for you, pal:D
Finally solved C with 2 seconds on timer :( That's embarrassing.
me to.
How to do Div2 c Geometric progrssion?
You can support 2 maps, left and right. When you iterate over the sequence, you should add left.get(a[i] / k) * right.get(a[i] * k) to the answer, and then add current element a[i] to the left map and remove it from the right one.
Spent 30 minutes trying to find the problem with this attempt at problem C. Can someone lend a hand?
http://pastie.org/private/mmg81uzwfniinmxabqa2rw
k * k overflows.
EDIT: Result (num) could overflow too.
It returns 0, regardless of input. I didn't even have time to consider overflows haha.
Я уже и забыл, как дооолго запускаются систесты.
What was test case 5 of D? I used a solution that kept track of valid intervals where battleships could be placed: if bob's shot interrupted an interval, then I split it into 2 intervals, and for each interval I calculated IntervalSize / SizeOfShip. If this was less than NumberOfShips, then I printed that index and stopped the program. At the very end I printed -1 and ended to catch the case where it is undeterminable. What is wrong with this approach?
Ships cannot touch each other.
What's the intended solution on D?
I tried keeping a sorted vector of pairs, representing all uninterrupted segments where you can place ships. Every time you fire a shot, you find the segment that shot is in and split the segment in two. Used binary search to make the segment searching faster, but my solution was wrong on case 5.
Is the idea wrong, or did I mess up my implementation?
How do you calculate the number of ships that can be placed into one interval?
interval size / size of ship
Yeah, that's wrong. They must be non touching. I saw this only after a lot of wrong submissions :D
Let there be maximum of x ships of size a in the interval of size n.
Then x*a+(x-1)<=n
hence, x=(n+1)/(a+1)
Idea is ok. Alternative solution is to do binary search over result.
I processed the queries from last to begin and kept a disjoint set for the connected parts and instead of splitting merging.
Apparently, you can't have 2 ships RIGHT next to each other, so when calculating number of ships possible in an arrangement, you had to make sure you left 1 space in between each(so you had to add extra logic for both inside the interval, as well as between consecutive intervals.
My solution was binary searching for the answer. You fix the amount of shots fired then you mark those cells. Once you've marked some cells as shot you can get the maximum amount of ships that can be placed in O(N) using greedy approach.
1) Let's find the asnwer by binary search (answer —
k) 2) Each iteration of search we will check by function CHECKING that says TRUE if we can't place all ships withkturns and FALSE if we can. If True, you should makeleft_border=k, and if False —right_border=k+13) How does CHECKING work? Make a vector of field and fill it by1(free place) and2(place where Bob shooted). Then in cycle just greedy fill it by ships from left to right and calculate its total. Returntotal<number_of_ships4) PROFIT!Eh, I believe the "two weapons cannot touch" part in D should have been explained more clearly... I was thinking it just meant a cell cannot belong to more than one weapon (and I guess so did everyone getting WA on pretest 5).
The same thing happened with me. I spent 2 hours making numerous test cases and my code was working for all of them.
So , after the contest , upon asking adurysk I realized that two ships could not "touch" meant they couldn't be adjacent . Facepalm
Needed to change (N/K) to (N+1)/(K+1) to get it Accepted :P
It was written both in statement and in input section. How could it be explain more clearly?
It just said "the ships cannot intersect and even touch each other"- it would be better if the problemsetter explicitly mentioned that you cannot place two weapons right next to each other.
The author separately mentioned intersecting and touching, shouldn't that be a hint that these describe two distinct situations?
The round was awsome. I enjoyed a lot E and F. Congrats for the round. Also , was F a dp in O(N^3*K) ?
My F was O(n ^ 2 + nk) i think
Mine is O(N^2 * K) afterall ( http://mirror.codeforces.com/contest/567/submission/12374862 ) , but it can be done in your complexity.
Can someone help how to solve C ?? :(
two maps
m1[x] = y <=> count of subsequence of length one finishing at x equals y
m2[x] = y <=> count of subsequence of length tho finishing at x equals y
So, we getting num a. Then ans += m2[a/k]; m2[a] += m1[a/k]; m1[a]++
sorry but i didnt get u ??
If we've got num a, how many subsequence of length one finishing at a? As many as subsequences of length two finishing at a/k. So ans += m2[a/k]
Analogycal, how many subsequences of length two finishing at a? As many as subsequences of length one finishing at a/k. So m2[a] += m1[a/k]
m1[a]++ because we've got new subsequence of length one finishing at a.
What was the idea for keeping track of the number of shortest path? Does it use Dijkstra?
Can anyone who solved F explain a solution? The problem seemed like hell to me :D
DP; you put the pairs from largest to smallest. States are "the blocks you put so far are in the interval [i,j]". There are just 3 possible transitions from any state and you just need to check if any in/equality becomes invalid for each of them.
The simplest implementation is O(KN3), which definitely passes.
dp[left][right] — in how many ways can we fill blocks 1... left and right... 2N with small numbers (numbers lower that those left for interval left + 1... right - 1. We must consider 3 cases: adding two new equal numbers in left + 1, left + 2, or in left + 1, right - 1, or in right - 2, right - 1. For all 3 cases we must check is everything would be ok for them — those two places are equal to each other but lower than remaining places in left + 1... right - 1.
OMG i forgot to remove debugging code and the stderr flushes made me TLE on problem D.... ;(
http://mirror.codeforces.com/contest/567/submission/12367438
use tab indent to understand your bug!!
There are no bugs there, its just that i'm writing a bunch of endl's to cerr (which i used while working in the problem), and i didn't remove them before submitting....
Can anyone explain me how to solve problem D??
One way is to find result by binary search. Then, we mark some cells as blocked and we need to count maximal possible number of ships. Say if you need more explanation.
Yeah can you elaborate it more??
which part?
Here binary Search will be applied on what?And then How cells can be marked as blocked??
Binary search on result — size of prefix of given blocked cells. Cells can be marked as blocked with array of booleans. Then we iterate from 1 to size_of_grid and calculate number of ships we can have.
The rough idea is to maintain the maximum number of ships you can put on the board.
Notice the fact when you hit a spot, you are splitting an interval(between 2 previously-hit spots) into 2 intervals. With that, you can calculate how many ships can be put on the original interval and on these new 2 intervals, and update the number we're maintaining.
Use std::set to store previously-hit spots.
Let's use a some set, which will keep disjoint segments.
Also let's keep some value
Twhich means what is the maximum number of ships we can arrange on a board.When we add a segment to the set, we must increase
Tby some valuex, which means the maximum number of the ships we can arrange on current segment. This number is equal to(len + 1) / (a + 1)wherelenis a length of the segment andais the length of the shipAt first let's add segment
(1, n)to the set.So, when the cell
cis coming, let's find a some segment(l, r)which keepsc(l <= c <= r). We decreaseTby(len(l, r) + 1) / (a + 1).Then we add segments
(l, c - 1)and(c + 1, r)to the set and increaseTby appropriated values.If we processed current operation and
Tis less thank, answer will be equal to the number of operations we processed already.For keeping segment we can use a simple set of pairs. My solution: 12365410
Wow, I used to write a segment tree in that problem, but your solution is much more simple than mine, thanks!
Of course, you can use segment tree, but I think set is the simplest one.
Nice problems vovuh! I like C and F especially. Hope to see more rounds from you.
I got stuck (kept failing test case #13) in problem B. Embarrassing, but this was my first contest. Here is my solution:https://ideone.com/G5fuEl Can some one give me any ideas? I can't sleep, keep thinking about it :|.
You can view small inputs after the contest. Scroll to the end here: 12373900
In the if at line 29 you should add :
This is because the person left, but you never marked him coming in. So in the beginning of the iteration you added arr[i], marking him leaving, once you understand that he's been in all along you should make up for his coming.
Feel free to ask questions :)
Just one question I had in mind.. did you guys used some debugger when you were starting out?
Debug output is usually the fastest way. Just add some safeguards to your template to prevent it from working on the server side:
ONLINE_JUDGEis defined in the Codeforces environment.Your if "if(p[abs(arr[i])]<0){" should be done at most once for every arr[i]. You have WA for test
What is the idea of E?
My solution is to dijkstra 2 times, one from s and one from t
for each edge u->v if dist(s->u) + c(u,v) + dist(v, t) == dist(s, t), u->v may be a "sure" edge
Take all those edges and eliminate the direction, we can find the bridge by simple DFS.
Note that there may be multiple edges between two vertexes. I failed E during the contest because of that :(
In problem C, what would be the answer if
k=1??You could easily count how many times a given numbers repeats using a map, then it's basically C( [amount of repetitions of this number], 3) which is equal to [reps * (reps-1) * (reps-2)/6] when you simplify the formula.
Thanks, my code gave AC, unpredictable integer overflow at the contest -_-
Why is it unpredictable ?
For k=1 this program gives correct anserws. PS.a is
map<long long,long long>public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] t = new boolean[1000010]; int cap = 0; int cur = 0; for (int i = 0; i < n; i++) { String s = in.readLine(); String[] ar = s.split(" "); if (ar[0].charAt(0) == '+' && !t[Integer.valueOf(ar[1])]) { cur++; t[Integer.valueOf(ar[1])] = true; } else if (ar[0].charAt(0) == '-' && t[Integer.valueOf(ar[1])]) { cur--; } else if (ar[0].charAt(0) == '-' && !t[Integer.valueOf(ar[1])]) cap++; cap = Math.max(cap,cur); } out.print(cap); }
my code above for problem B is incorrect, because the bold line, without that line, the code is correct. But the number assigned to people is unique, why can someone take same number twice?
please paste your code here.
Спасибо balalaika, можете не обращать внимания.
lower_bound(Value) — первый элемент item >= Value
upper_bound(Value) — первый элемент item > Value
Да я знаю про это.
Можете дать тест, в котором они дают различные ответы?
Этот тест из задачи на котором ваша программа и валится
Не знаю, чем Test#8 не устроил, но я вижу такую ошибку:
Допустим, есть интервал (x, y). Вы стреляете по x. Тогда (x, y) должен превратиться в (x+1, y). В неверном вашем же коде представим себе ситуацию следующую: есть интервал (1 N). Стреляем по 1. Тогда у вас итератор будет указывать на несуществующий элемент, ибо вначале вернется итератор на (1 N), который есть begin(), а потом вы его декрементируете и работаете с несуществующим итератором.
Надеюсь, что помог.
спасибо, извините что затупил)
забьем на it-- пока. тогда в 1 случае итератор будет указывать на элемент, поле first которого строго больше x, во втором — не обязательно.
Рейтинга долго нет. С кодэфом что-то не так или опять бан читерам роздают?
рейтинга всегда долго нету видимо они по несколько раз его пересчитывают что бы не ошибиться...
а то что его компьютер считает это ничего?
Я же сказал что точно не знаю но думаю именно поэтому. Даже суперкомпьютеры иногда дают сбои а у кодфорцез обычные. Выводы делай сам!
Wow the problemsets are really nice. It's hard to believe that it's prepared by a blue coder.
That's because, this rating shows the measurement of competitive programming skill which is different from problem inventing skills. There are many cases where enough knowledge doesn't help the subject to do better in competitive programming.
Was this contest Unrated???
No.
Я, наверное, тупой, но в чем косяк? http://mirror.codeforces.com/contest/567/submission/12376471
там 2 * 100 * 1000 клеток. если исправить то проходит.
Да, спасибо, я уже увидел. Пойду в глаза чего-нибудь закапаю.
Can someone point out the mistake in this code?
Problem D
Thank you in advance.
it=s.upper_bound(mp(mov[i],-1));should beit=s.upper_bound(mp(mov[i],n+1));in order to find the intersecting interval after decrementing it. If you have an interval that starts at mov[i], upper_bound will return it and decrementing will miss it.Thanks a lot. Silly mistake, could have been avoided during the contest.
While solving E, i had to keep track of number of shortest paths passing through a particular edge. But this value can exceed 10^18. I used hashing modulo 2 large primes to keep track.
Is there any other (deterministic) workaround to this?
Yup, Bridges in the "shortest path graph" are guaranteed to be on every possible shortest path.
Woah, that's a great observation, thanks :)
used coordinate compression in c :P
It's just div 2, but I'm very happy anyway. Nice problems! :D
It's just div 2, but I'm very happy anyway. Nice problems! :D
Thanks for a great contest!
Hello, this is my first contest. I'm just curious about one thing : when does the rating change after a contest?
Hello, dear newcomer! You should now that right now Mike Mirzayanov, Zlobober and others are sitting at the round table and hotly-debate everyone's rating change. It takes a lot of time, you know. It was my not serious thought of things when I took part in my first contests. Now I think, that the question of looking for cheaters is hardtime. Maybe anyone know another 'why'?
Thanks for the answer, I expected it to be more automatically updated. Great to know that they look for cheaters.
Mia rating
Your problems are really amazing. Thank you :)
Подскажите, пожалуйста, в чем ошибка?
http://mirror.codeforces.com/contest/567/submission/12378484
Посмотри на свой ответ и на ответ жюри. По нему очевидно, что у тебя переполнение. Замени все на лонги.
P.S. при том очевидно, в каком месте нужно заменить
Thank you for the contest. Can you update top 5 contestants as well :D ?
Update: Down voters, so you don't want to see your name when you are in top 5?
Can anybody help me check my code of problem E: http://mirror.codeforces.com/contest/567/submission/12382102
Thanks!
You haven't taken into account multiple edges while checking the YES condition
I think my code has covered this case. Can you give me a test case to illustrate it?
Yeah you are right you have taken that into account.
Deleted
Could someone explain this testcase (which is the 37th) of Problem E?
The output is NO for all edges except the two that lie on the unique shortest path of length 378, for which the answer is YES. What I don't understand is why the answer for all other edges is NO. Let's take for example the path (1 — 5 — 3 — 10 ) of length 470. The first and the last edge could be reduced by 93 to give a path of length 377 in which case they lie on the unique shortest path. I probably misunderstood something in the problem statement. Thanks in advance.
I had the same problem.
In the statement it says The road is directed from city ai to city bi. In this test case you can't go from 5 to 3 and therefore the path (1 — 5 — 3 — 10) doesn't exist.
It's my first contest in codeforces and I enjoyed it very much. Wish your next round,and I hope I can do better then.
could someone tell me why this solution gives TLE for problem D? It's run in O( m log(m) ) 12387839
:p :p
Not too sure about the TLE, but my suspicion is your set of ints. You should hold your intervals/segments as pairs of ints. Modify your program accordingly and it should pass.
No you don't need to. Refer to my submission
Lower (or upper) bound has linear complexity on set. Use set.lower_bound(value) instead. (logn)
got AC :) thanks for this information I didn't know that lower_bound have linear complextiy on set kpw29.
12399997 AC
Кто-нибудь может объяснить мне, в чём смысл предварительной регистрации?! Из-за неё пропустил соревнование :(
Здесь был тупой комент
Ерунда. Предварительная регистрация нужна для распределения по комнатам. В контестах по правилам ACM (давно же их тут не было) регистрация часто не прекращается даже после начала контеста.
I am not from the top 5, but I love to see the winners' names in the updates :)
Подскажите пожалуйста, а в раундах только индивидуальное участие допускается? Команда может участвовать или нет?
Смотря в каких раундах. В обычных только индивидуальное участие, в специальных иногда могут соревноваться и команды.