Submission #164003

#	Time	Username	Problem	Language	Result	Execution time	Memory
164003		TadijaSebez	절취선 (JOI14_ho_t5)	C++11	100 / 100	2927 ms	126668 KiB

2014_ho_t5

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mt make_tuple
#define ll long long
const int N=100050;
int X1[N],X2[N],Y1[N],Y2[N];
vector<tuple<int,int,int>> events;
int ls[N],rs[N],pri[N],val[N],idx[N],tsz,root,sum[N],tag[N],deg[N],sz[N],L[N],R[N];
bool ban[N];
int Make(int v, int i)
{
    tsz++;
    pri[tsz]=rand()+(rand()<<15);
    val[tsz]=v;
    sz[tsz]=1;
    deg[tsz]=0;
    L[tsz]=R[tsz]=v;
    idx[tsz]=i;
    sum[tsz]=tag[tsz]=ls[tsz]=rs[tsz]=0;
    return tsz;
}
void upd(int x, int f){ if(x) sum[x]=sz[x],deg[x]+=f,tag[x]+=f;}
void push(int x){ if(tag[x]) upd(ls[x],tag[x]),upd(rs[x],tag[x]),tag[x]=0;}
void pull(int x)
{
    if(!x) return;
    push(x);
    sz[x]=sz[ls[x]]+1+sz[rs[x]];
    sum[x]=sum[ls[x]]+(deg[x]!=0)+sum[rs[x]];
    L[x]=ls[x]?L[ls[x]]:val[x];
    R[x]=rs[x]?R[rs[x]]:val[x];
}
void Split(int x, int &l, int &r, int v)
{
    if(!x) l=r=0;
    else
    {
        push(x);
        if(val[x]<v) l=x,Split(rs[x],rs[l],r,v);
        else r=x,Split(ls[x],l,ls[r],v);
        pull(x);
    }
}
void Split3(int x, int &a, int &b, int &c, int l, int r)
{
    Split(x,a,b,l);
    Split(b,b,c,r+1);
}
void Merge(int &x, int l, int r)
{
    if(!l || !r) x=l^r;
    else
    {
        if(pri[l]>pri[r]) push(l),x=l,Merge(rs[x],rs[l],r);
        else push(r),x=r,Merge(ls[x],l,ls[r]);
        pull(x);
    }
}
void Merge3(int &x, int a, int b, int c)
{
    Merge(x,a,b);
    Merge(x,x,c);
}
void Ins(int &x, int v, int i)
{
    int a,b,c;
    Split(x,a,c,v);
    b=Make(v,i);
    Merge3(x,a,b,c);
}
void Del(int &x, int v)
{
    int a,b,c;
    Split3(x,a,b,c,v,v);
    Merge(x,a,c);
}
void Mark(int &x, int l, int r)
{
    int a,b,c;
    Split3(x,a,b,c,l,r);
    upd(b,1);
    Merge3(x,a,b,c);
}
int Get(int &x, int l, int r)
{
    int a,b,c;
    Split3(x,a,b,c,l,r);
    int ans=sum[b];
    Merge3(x,a,b,c);
    return ans;
}
int SZ(int &x, int l, int r)
{
    int a,b,c;
    Split3(x,a,b,c,l,r);
    int ans=sz[b];
    Merge3(x,a,b,c);
    return ans;
}
int Pre(int x, int v)
{
    if(!x) return 0;
    push(x);
    if(val[x]<=v)
    {
        if(rs[x] && L[rs[x]]<=v) return Pre(rs[x],v);
        else return x;
    }
    else return Pre(ls[x],v);
}
void init(){ tsz=root=0;}
int D[N],q;
void DegSweep()
{
    init();
    for(int i=1;i<=q;i++)
    {
        if(X1[i]==X2[i]) events.pb(mt(X1[i],2,i));
        else events.pb(mt(X1[i],1,i)),events.pb(mt(X2[i],3,i));
    }
    sort(events.begin(),events.end());
    for(auto e:events)
    {
        int x,t,i;tie(x,t,i)=e;
        if(t==1) Ins(root,Y1[i],i);
        if(t==2)
        {
            int a,b,c;
            Split3(root,a,b,c,Y1[i],Y2[i]);
            D[i]=sz[b];
            Merge3(root,a,b,c);
            Mark(root,Y1[i],Y2[i]);
        }
        if(t==3)
        {
            int a,b,c;
            Split3(root,a,b,c,Y1[i],Y1[i]);
            D[i]=deg[b];
            Merge(root,a,c);
        }
    }
}
queue<int> Q;
const int H=2*N;
const int M=2*H;
struct Compress
{
    vector<int> all;
    Compress(){}
    void Add(int x){ all.pb(x);}
    int Find(int x){ return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
    void Build(){ sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());}
} xs,ys;
struct SegmentTree
{
    set<pair<int,int>> node[M];
    SegmentTree(){}
    void Add(int x, int l, int r, int i)
    {
        for(l+=H,r+=H;l<=r;l>>=1,r>>=1)
        {
            if(l%2==1) node[l++].insert({x,i});
            if(r%2==0) node[r--].insert({x,i});
        }
    }
    void Take(int i, int l, int r, bool one)
    {
        for(i+=H;i;i>>=1)
        {
            for(auto it=node[i].lower_bound({l,-1e9});it!=node[i].end() && it->first<=r;)
            {
                int j=it->second;
                if(ban[j]){ node[i].erase(it++);continue;}
                if(one)
                {
                    D[j]--;
                    if(D[j]<=1) Q.push(j),ban[j]=1,node[i].erase(it++);
                    else it++;
                }
                else
                {
                    Q.push(j);
                    ban[j]=1;
                    node[i].erase(it++);
                }
            }
        }
    }
} ST[2];
void Build()
{
    DegSweep();
    for(int i=1;i<=q;i++) xs.Add(X1[i]),xs.Add(X2[i]),ys.Add(Y1[i]),ys.Add(Y2[i]);
    xs.Build();ys.Build();
    for(int i=1;i<=q;i++)
    {
        if(D[i]<=1) Q.push(i),ban[i]=1;
        else
        {
            if(X1[i]==X2[i]) ST[0].Add(xs.Find(X1[i]),ys.Find(Y1[i]),ys.Find(Y2[i]),i);
            else ST[1].Add(ys.Find(Y1[i]),xs.Find(X1[i]),xs.Find(X2[i]),i);
        }
    }
    while(Q.size())
    {
        int i=Q.front();
        Q.pop();
        if(X1[i]==X2[i]) ST[1].Take(xs.Find(X1[i]),ys.Find(Y1[i]),ys.Find(Y2[i]),1);
        else ST[0].Take(ys.Find(Y1[i]),xs.Find(X1[i]),xs.Find(X2[i]),1);
    }
}
int CntCmp()
{
    int ans=0;
    for(int i=1;i<=q;i++) if(!ban[i])
    {
        ans++;
        Q.push(i);
        ban[i]=1;
        while(Q.size())
        {
            int j=Q.front();
            Q.pop();
            if(X1[j]==X2[j]) ST[1].Take(xs.Find(X1[j]),ys.Find(Y1[j]),ys.Find(Y2[j]),0);
            else ST[0].Take(ys.Find(Y1[j]),xs.Find(X1[j]),xs.Find(X2[j]),0);
        }
    }
    return ans;
}
int main()
{
    srand(time(0));
    int n,m;
    scanf("%i %i %i",&n,&m,&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]);
    }
    q++;X1[q]=X2[q]=0;Y1[q]=0;Y2[q]=m;
    q++;X1[q]=X2[q]=n;Y1[q]=0;Y2[q]=m;
    q++;Y1[q]=Y2[q]=0;X1[q]=0;X2[q]=n;
    q++;Y1[q]=Y2[q]=m;X1[q]=0;X2[q]=n;
    Build();
    events.clear();
    for(int i=1;i<=q;i++) if(!ban[i])
    {
        if(X1[i]==X2[i]) events.pb(mt(X1[i],2,i));
        else events.pb(mt(X1[i],1,i)),events.pb(mt(X2[i],3,i));
    }
    sort(events.begin(),events.end());
    ll a=0,b=0;
    init();
    for(auto e:events)
    {
        int x,t,i;tie(x,t,i)=e;
        if(t==1) Ins(root,Y1[i],i);
        if(t==2)
        {
            int node=Pre(root,Y2[i]);
            assert(node!=0 && val[node]>=Y1[i]);
            a+=Get(root,Y1[i],val[node]-1);
            assert(SZ(root,Y1[i],val[node]-1)>0);
            if(deg[node]==0) b++;
            Mark(root,Y1[i],Y2[i]);
        }
        if(t==3) Del(root,Y1[i]);
    }
    ll ans=a-b;
    ans+=CntCmp();
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:235:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i %i",&n,&m,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:238:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50