naivedyam's blog

Why WA at test 8?
By naivedyam, history, 2 hours ago, In English

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?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
109 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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]

→ Reply
  • »
    »
    98 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
97 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Why WA at test 8?

Bcz its wrong

→ Reply
  • »
    »
    93 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
32 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply