Submission #163934

#	Time	Username	Problem	Language	Result	Execution time	Memory
163934		TadijaSebez	절취선 (JOI14_ho_t5)	C++11	0 / 100	3 ms	376 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],tsz,root,sum[N],tag[N],fir[N],sz[N],L[N],R[N];
int Make(int v)
{
    tsz++;
    pri[tsz]=rand()^rand();
    val[tsz]=v;
    sz[tsz]=1;
    fir[tsz]=1;
    L[tsz]=R[tsz]=v;
    return tsz;
}
void upd(int x){ if(x) sum[x]=sz[x],fir[x]=0,tag[x]=1;}
void push(int x){ if(tag[x]) upd(ls[x]),upd(rs[x]),tag[x]=0;}
void pull(int x)
{
    if(!x) return;
    sz[x]=sz[ls[x]]+1+sz[rs[x]];
    sum[x]=sum[ls[x]]+(1-fir[x])+sum[rs[x]];
    L[x]=ls[x]?L[ls[x]]:val[x];
    R[x]=rs[x]?R[rs[x]]:val[x];
}
void rot_l(int &x){ int y=rs[x],z=ls[y];rs[x]=z;ls[y]=x;pull(x);pull(y);x=y;}
void rot_r(int &x){ int y=ls[x],z=rs[y];ls[x]=z;rs[y]=x;pull(x);pull(y);x=y;}
void Ins(int &x, int v)
{
    if(!x) x=Make(v);
    else
    {
        push(x);
        if(val[x]<v)
        {
            Ins(rs[x],v);
            if(pri[rs[x]]>pri[x]) rot_l(x);
        }
        else
        {
            Ins(ls[x],v);
            if(pri[ls[x]]>pri[x]) rot_r(x);
        }
        pull(x);
    }
}
void Del(int &x, int v)
{
    if(!x) return;
    push(x);
    if(val[x]==v)
    {
        if(!ls[x]) x=rs[x];
        else if(!rs[x]) x=ls[x];
        else if(pri[ls[x]]>pri[rs[x]]) rot_r(x),Del(rs[x],v);
        else rot_l(x),Del(ls[x],v);
    }
    else if(val[x]<v) Del(rs[x],v);
    else Del(ls[x],v);
    pull(x);
}
int Get(int x, int qs, int qe)
{
    if(!x || L[x]>qe || R[x]<qs) return 0;
    if(L[x]>=qs && R[x]<=qe) return sum[x];
    push(x);
    return Get(ls[x],qs,qe)+Get(rs[x],qs,qe);
}
void Mark(int x, int qs, int qe)
{
    if(!x || L[x]>qe || R[x]<qs) return;
    if(L[x]>=qs && R[x]<=qe) return upd(x);
    push(x);
    Mark(ls[x],qs,qe);
    Mark(rs[x],qs,qe);
    pull(x);
}
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);
}
int main()
{
    srand(time(0));
    int n,m,q;
    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;
    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());
    ll a=0,b=0;
    for(auto e:events)
    {
        int x,t,i;tie(x,t,i)=e;
        if(t==1) Ins(root,Y1[i]);
        if(t==2)
        {
            a+=Get(root,Y1[i],Y2[i]);
            int node=Pre(root,Y2[i]);
            int f=fir[node];
            Mark(root,Y1[i],Y2[i]);
            if(node && val[node]>=Y1[i] && Get(root,Y1[i],Y2[i])>1 && f) b++;
        }
        if(t==3) Del(root,Y1[i]);
    }
    ll ans=a-b;
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:97: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:100: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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50