My submission 290383236 for the problem 1234D - Distinct Characters Queries is giving a WA at test case 8. However the numbers differ at case 303 so I cant view that particular test case. I don't get what am I doing wrong as the logic seems fine to me (Segment trees are some real pain while debugging). Can someone help me out here?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:24:05
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:24:05
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 04:10:56 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Why would you use segtree for div3 D? :). I guess you know the approach but simply the idea should be to store the indices of occurence of characters (since there are only 26 of them). And then use binary search to check for all characters if character occurs between [l,r]
I wasn't upsolving it as a contest I am currently learning and solving problems of segment tree that's why preferring to use it as much as possible (for learning purposes only) and I can't solve those 2000 rated ones yet so 1600 ones are comfortable to start from.
Bcz its wrong
That's what I am asking what part of it is giving WA. Even knowing the particular test case where it gets WA would help a lot (I can't stress test yet)
Why on earth would you pass update(1,0,n-1,pos-1,c) when you already did take care of pos as 0-indexed in update function.
Not doing so gets it fail on test 2 itself
But obviously you don't do pos-1 at two places
Test Case :
rfkqyuqf 10 1 6 y 1 4 n 2 1 2 1 8 r 2 1 6 2 4 7 1 8 v 1 1 l 1 2 p 2 4 6
Expected output : 2 5 3 2
Your output : 2 6 5 5
My submission for reference, even I used segment tree
in update function change pos — 1 to pos
(remove -1 from these line)
char original = arr[pos -1];
arr[pos -1] = val;
290406472 (updated code)
Thanks! That helped a lot!
This might be too silly of a question again but I made another submission implementing the same logic differently in 290449046. In the AC code we keep the pos as it is in update function and do call pos — 1 in main function. However here we are calling pos in main function and taking care of the indexing in the update function. Aren't both equivalent? Then why is the other one giving wa?
Nope, Both are different because ur segment tree is 0 based indexed so every decision should be based on Zero based indexing and u are doing the same in ur updated submission while in ur first submission from main function u r sending a zero based indexing index so u should access it like main index in ur segment tree but ur first(WA) code will treat it as one based indexing when it is reaching at its base condition in update function. which is wrong. Just think that if u have to update index 0 then in ur first code (Which is giving WA) when it reaches to the base case then it will try to access index pos — 1 => 0 — 1 -> -1 Which will produce RE(Runtime Error).
Got it. Thanks!
Check my submission for correction.