Блог пользователя codeworrior

Автор codeworrior, 14 лет назад, По-английски
i m doing this problem on spoj..i cant find any approach fr this..bt i feel this is to be done by sweep lines...hw to do this prob using sweep lines or by any other method??
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You can first compress coordinates and then use interval trees to determine if a poster is visible going from the last poster to the first one.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think it's also possible with sorting and sweeping.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I solved with just STL set
    • 9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how did you do it with set ? can you please give me your code and idea.

      this is my code.but its getting WA :(

      #include<bits/stdc++.h>
      using namespace std;
      int ks,kase,n,seen;
      pair<int,int>pos[40010];
      set<int>S;
      int main()
      {
          scanf("%d",&kase);
          for(ks=1;ks<=kase;ks++)
          {
              scanf("%d",&n);
              S.clear();
              seen=0;
              for(int i=0;i<n;i++)
              {
                  scanf("%d %d",&pos[i].first,&pos[i].second);
                  S.insert(pos[i].first);
                  S.insert(pos[i].second);
              }
              set<int>::iterator it,jt;
              for(int i=n-1;i>=0;i--)
              {
                  it=S.lower_bound(pos[i].first);
                  jt=S.lower_bound(pos[i].second);
                  if(it!=jt )
                  {
                      seen++;
                      S.erase(it,jt);
                  }
              }
              printf("%d\n",seen);
          }
      }