#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct init
{
    int L,R;
};
struct node
{
    int L,R;
    int mid()
    {
        return (L+R)/2;
    }
    bool iscover;
};
init pos[10100];//海报位置信息
int x[20100]; //边界坐标信息
node a[800100];
int Hash[10000100];
void build(int root,int l,int r)
{
    a[root].L=l;
    a[root].R=r;
    a[root].iscover=0;
    if(l==r)
        return ;
    else
    {
        build(root*2,l,a[root].mid());
        build(root*2+1,a[root].mid()+1,r);
    }
}
bool post(int root,int l,int r)  // return 1 : not cover
{
    if(a[root].iscover == 1)
        return 0;
    if(a[root].L == l && a[root].R ==r)
    {
        a[root].iscover = 1;
        return 1;
    }
    bool rec;
    if(r<=a[root].mid())
        rec = post(root*2,l,r);
    else if(l>a[root].mid())
        rec = post(root*2+1,l,r);
    else
    {
        bool r1=post(root*2,l,a[root].mid());
        bool r2=post(root*2+1,a[root].mid()+1,r);
        rec = r1||r2;
    }
    if(a[root*2].iscover && a[root*2+1].iscover)
        a[root].iscover=1;
    
    return rec;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int all=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&pos[i].L,&pos[i].R);
            x[all++]=pos[i].L;
            x[all++]=pos[i].R;
        }
        sort(x,x+all);
        all = unique(x,x+all)-x; //qu chong
        /*
        int hash_num=1;
        Hash[x[0]]=1;
        for(int i=1;i<all;i++) // li san hua
        {
        
            if(x[i]==x[i-1]+1)  // important
            {
                Hash[x[i]]=++hash_num;
            }
            else
            {
                Hash[x[i]]=hash_num+2;
                hash_num+=2;
            }
        }
         */
        int hash_num=0;
        for(int i=0;i<all;i++)
        {
            Hash[x[i]]=hash_num;
            if(i<all-1)
            {
                if(x[i+1]-x[i]==1)
                    hash_num++;
                else
                    hash_num+=2;
            }
        }
        int ans=0;
        build(1,0,hash_num);
        for(int i=n-1;i>=0;i--) //dao xu
            if(post(1,Hash[pos[i].L],Hash[pos[i].R]))
                ans++;
        
        printf("%d\n",ans);
    }
    return 0;
}

• Re:我累个去。。我的也是C++WA，G++AC (1459) changmu 2014-09-06 00:21:20
  • Re:我累个去。。我的也是C++WA，G++AC (1591) zero6842 2015-01-02 10:58:18
    • Re:我累个去。。我的也是C++WA，G++AC (10) zero6842 2015-01-02 10:58:39
      • 我是G++ TLE ，C++过了－ － (33) cyx354200 2015-06-04 22:42:06