• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            a tutorial on computer science

              C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              21 隨筆 :: 0 文章 :: 17 評(píng)論 :: 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之間的第一個(gè)比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 閱讀(190) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            精品久久久久中文字幕一区| 久久成人精品视频| 久久精品国产福利国产琪琪| 国产午夜久久影院| 91精品观看91久久久久久| 日韩欧美亚洲综合久久影院Ds| 超级碰碰碰碰97久久久久| 久久婷婷国产综合精品| 国产—久久香蕉国产线看观看 | 亚洲AV成人无码久久精品老人| 亚洲AV无码久久精品色欲| 国内精品久久久久影院网站| 久久精品一区二区三区AV| 亚洲国产精品人久久| 人妻无码精品久久亚瑟影视 | 久久99国产精品成人欧美| 亚洲精品无码久久久久| 蜜臀久久99精品久久久久久| 久久亚洲AV成人无码电影| 色婷婷久久久SWAG精品| 久久精品国产一区二区三区日韩| 亚洲伊人久久成综合人影院| 亚洲国产精品久久久久婷婷软件| 少妇精品久久久一区二区三区 | 久久青青草原亚洲av无码app | 久久发布国产伦子伦精品| 久久国产精品免费一区二区三区| 久久久久无码精品国产不卡| 亚洲国产高清精品线久久| 99久久精品这里只有精品 | 久久久久亚洲AV成人网| 久久国产精品久久| 久久天天躁狠狠躁夜夜网站| 久久天天躁夜夜躁狠狠躁2022| 久久男人中文字幕资源站| 青青热久久综合网伊人| 97精品久久天干天天天按摩| 久久亚洲精品成人AV| 久久99精品国产麻豆| 国产精品成人无码久久久久久| 91久久精一区二区三区大全|