pranshul's blog

Help with Round #283(Div. 1 C)
By pranshul, 10 years ago, In English

I have tried to implement the solution for http://mirror.codeforces.com/problemset/problem/496/E based on what I could understand by translating the editorial to english. My code is failing on 10th test case. Please help me find a bug in my code. Thanks in advance. :)

http://mirror.codeforces.com/contest/496/submission/9187611

EDIT: Accepted!!

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have the same problem with you, i failed on the 15 test. What was your mistake? link to my code

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

    I don't think using a pair as an index in mymap will work as you can see in the fourth test case, more than one actor can have same pair of (ci,di) . What I did was keep a unique index with each actor and use it to identify the map and the set( with di being the other variable in the set of pair).

    Thus, map[idx]=(ci,ki) and set.insert=(di,idx);

    Also I inserted di in the set instead of ci as we need to be greedy and pick the actor with di just larger than bi.

    ci<=ai<=bi<=di

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

      Actually i use map pair to store the upper bound of the singer and the index of the singer, so it will not overlap. My mistake is much simpler, where the second iterator for the singer only from 1 to n. while(cs[j].X.X<=bh[i].X.X&&j<=n) It should be while(cs[j].X.X<=bh[i].X.X&&j<=m) Thanks a lot to angelg who helped me and also pranshul for reading my code and answer my comment.

      → Reply