a tutorial on computer science

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 17 评论 :: 0 Trackbacks
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn =  210000+20;
const int INF = 1<<29;
using namespace std;
int N;
struct Node
{
  char op[6];
  int x,y,pos;
};
vector<Node> hh;
int rmost[maxn*8],cnt[maxn*8],hpos[maxn*8];
bool operator< (const Node& a,const Node& b)
{
  if(a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}
bool operator== (const Node& a,const Node& b)
{
  if(a.x == b.x&&a.y==b.y) return true;
  return false;
}
void add(int pos,int ll,int rr,int idx)
{
   if(ll == rr)
   {
     rmost[idx] = hh[pos].y;
     cnt[idx]++;
     hpos[idx] = pos;
     return; 
   }
   int mid = (ll+rr)/2;
   if(pos <= mid)
     add(pos,ll,mid,idx*2);
   else
     add(pos,mid+1,rr,idx*2+1);
 
   cnt[idx] = cnt[idx*2] + cnt[idx*2+1];
   rmost[idx] = max(rmost[idx*2],rmost[idx*2+1]);
}
void del(int pos,int ll,int rr,int idx)
{
  if(ll == rr)
  {
    cnt[idx]--;
    if(cnt[idx] == 0)
      rmost[idx] = -1;
    return;
  }
   int mid = (ll+rr)/2;
   if(pos <= mid)
     del(pos,ll,mid,idx*2);
   else
     del(pos,mid+1,rr,idx*2+1);
  
  cnt[idx]--;
  rmost[idx] = max(rmost[idx*2],rmost[idx*2+1]);
}
int query(int l,int ll,int rr,int y,int idx)//l和r之间的第一个比y大的
{
  if(ll == rr)
  {
    if(cnt[idx] > 0 && rmost[idx] > y)
      return hpos[idx];
    return -1; 
  }  
 int mid = (ll+rr)/2;
 int nret = -1;
 if(l<=mid && rmost[idx*2] > y) nret = query(l,ll,mid,y,idx*2);
 if(nret == -1 && rmost[idx*2+1] > y) nret = query(l,mid+1,rr,y,idx*2+1);
 return nret;
}
int main()
{
   int i,j;
   int casenum = 1;
   while(scanf("%d",&N)!=EOF && N)
  {
  hh.clear();
    if(casenum != 1) printf("\n");
    printf("Case %d:\n",casenum++);
    hh.clear();
    memset(cnt,0,sizeof(cnt));
    memset(rmost,0,sizeof(rmost));
    vector<Node> vec;
    Node tmp;
    for(i=0;i<N;i++)
    {
      scanf("%s%d%d",tmp.op,&tmp.x,&tmp.y);
      vec.push_back(tmp);
      hh.push_back(tmp);
    }
    sort(hh.begin(),hh.end());
    hh.erase(unique(hh.begin(),hh.end()),hh.end());
    for(i=0;i<N;i++)
    {
      vec[i].pos = lower_bound(hh.begin(),hh.end(),vec[i]) - hh.begin();
    }
   for(i=0;i<N;i++)
   {
     if(vec[i].op[0] == 'a')
   add(vec[i].pos,0,hh.size()-1,1);
     else if(vec[i].op[0] == 'r') 
   del(vec[i].pos,0,hh.size()-1,1);
     else
     {
      for(j=vec[i].pos;j<hh.size();j++)
        if(hh[j].x > vec[i].x)
          break;
       if(j == hh.size()) 
       {
        printf("-1\n");
        continue;
       }
       int num = query(j,0,hh.size()-1,vec[i].y,1);
       if(num == -1) printf("-1\n");
       else
          printf("%d %d\n",hh[num].x,hh[num].y);
     }
   }
  }
  return 0;
}
posted on 2012-07-26 12:14 bigrabbit 阅读(171) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理