PKU 2528 Mayor's posters

http://poj.org/problem?id=2528

n枚のポスターを適当な順番で貼っていく時に、一部分でも見えているものは何枚あるかを数えろというような問題。

最初セグメントツリーでやろうとしたら、全然TLEが取れなかったので左端、右端をソートして順番に処理していく方針に変更しました。

解いている人の数がやたら多いですが、個人的にはそんなに簡単だと思えないので、謎です

int n;
pair<PI,int> in[20000];

void solve(){
  scanf("%d",&n);

  rep(i,n){
    int l,r;
    scanf("%d%d",&l,&r);
    in[i*2]=mp(mp(l,i),0);
    in[i*2+1]=mp(mp(r+1,i),1);
  }
  sort(in,in+2*n);

  set<int> ans;
  set<int> app;
  rep(i,2*n){
    if(!app.empty()) ans.insert(*app.begin());
    int j=i;
    while(j<2*n && in[i].F.F==in[j].F.F){
      if(in[j].S==0) app.insert(-in[j].F.S);
      else app.erase(-in[j].F.S);
      ++j;
    }
    i = j-1;
  }

  cout << SZ(ans) << endl;
}

main(){
  int t;
  scanf("%d",&t);
  rep(i,t) solve();
}