→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 18:17:52 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
blah blah blah (so that this blog goes to recent actions)
How to solve the 4th problem(120 points) ? How to obtain the best and worst rank for the contestants ?
The idea is to find for each contestant how many contestants will beat him for sure and how many contestants will he beat for sure. It can be done with 2D Binary indexed tree in O(N* log^2 N) :)
Edit: It's not log^2 N, it's actually log^2 700 so let's say O(N * 20).
We can actually use a 1D BIT and accomplish the same thing. Just sort the contestants by score in contest 1, and iterate through the list while updating the BIT with the score from the second contest.
Actually , We don't need neither 2D BIT nor 1D BIT , 2D partial sum is enough because the array is only 650*650 and we don't need to update it.
Yes, I saw what did Xellos write and now I'm asking myself why did I use BIT :D :D :D
For a fixed person p, best rank: all that have strictly more points in the previous round have higher ranks total; if they all get 650 and p also gets 650 (anyone else gets 0) in the 3rd round, then nobody else will be better than p.
Worst rank: anyone that has at least as many points as p in at least one contest (except p) can get 650 in the 3rd contest and be better, with one exception: if p has 650 in that contest and that other person has 0.
You can compress everyone into a 651 × 651 table, then count in O(6512) the number of people better/worse in both contests and compute the answers directly from that (+ checking the special case).
I did this exactly.. but only got 80 points D:<
Then you probably handled the special case wrong (I got full score this way).
oh wow ._________.
tricky tricky
2D BIT submitted in the last 30 seconds!(problem D — COCI)
in problem C i wanted to find the perimeter by doing this for every component ans += MaxLen(max length of component)*2 + R(rightmost) — L(leftmost) + 1 so any ideas what my problem is
Can someone help with problem COCI please?
I can't find out what is wrong with my code.
PS I guess only problem is with the way I calculate lowest possible rank (as all mismatch element numbers are even).
The way you calculate lowest possible rank is wrong. If person A gets 650 and x points in two previous rounds and there are D people who get (0, x), the worst rank of person A will be increased by D, not the number of all people getting from (0,0) to (0,x) as you do.
Secondly, Fenwick tree doesn't work with index 0, so be careful!
This code is Accepted: http://ideone.com/hlnoGb
Thank you very much :)
I blind coded the whole code in last 10 minutes of the contest. It was bloody hard to find the bug for me. Thank you again.
PS 0-indexed fenwick tree