I tried POI cards quite hard but failed to get the solution for 38% and 100% marks.Can anyone give a good hint to solve this question.Thanks in advance.
→ Pay attention
Before contest
Codeforces Round 940 (Div. 2) and CodeCraft-23
35:08:10
Register now »
Codeforces Round 940 (Div. 2) and CodeCraft-23
35:08:10
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 7 | SecondThread | 150 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/20/2024 06:26:51 (l1).
Desktop version, switch to mobile version.
Supported by
Naive solution: After every swap, compute result from scratch. Computing from scratch is going from left to right and always picking smaller of two values that is at least number chosen from previous card or reporting error.
To sped this up use a simple segment tree that does that quicker. For every base interval you keep two informations. If you start with smaller number on first card, which card will be chosen from last card or report error, and analogous information if we start with greater number on first card. Such informations are easily mergeable and we can get
complexity per query.