BZOJ AC 洛谷 90分
查看原帖
BZOJ AC 洛谷 90分
3843
BDF1楼主2017/2/20 19:43
#include<cstdio>
using namespace std;
int x[262144],y[262144],n,___,__,m,xx[262144],yy[262144];
bool o[262144];
#include<set>
#define P pair<int,int>
set<P>a[131072],b[131072];
set<P>::iterator A,B,C,D;
set<int>g;set<int>::iterator _;
int an,c[262144],d[262144];char e[262144],f[262144];
char file[16777216],*r=file-1;
#define cl(u,v,x,y) c[++an]=u,d[an]=v,e[an]=x,f[an]=y
bool chk(int x,int y){
    return a[x].lower_bound(P(y,0))->first==y;
}
bool check(int X,int Y,int z){
    if(chk(X,Y))return 0;
    int cnt=0;
    A=a[X].lower_bound(P(Y,0));if(A->second==z)cnt++;A--;if(A->second==z)cnt++;
    B=b[Y].lower_bound(P(X,0));if(B->second==z)cnt++;B--;if(B->second==z)cnt++;
    if(cnt<2)return 0;
    if(A->second==z)b[A->first].erase(P(X,z)),C=A,C++,a[X].erase(A),A=C;else A++;
    if(A->second==z)b[A->first].erase(P(X,z)),a[X].erase(A);
    if(B->second==z)a[B->first].erase(P(Y,z)),C=B,C++,b[Y].erase(B),B=C;else B++;
    if(B->second==z)a[B->first].erase(P(Y,z)),b[Y].erase(B);return 1;
}
int R(){
    int t=0;++r;
    while(*r<48)++r;
    while(*r>47)t+=t+(t<<3)+*r-48,++r;
    return t;
}
char S(){
    ++r;while(*r<48)++r;return *r;
}
int main(){
    fread(file,4096,4096,stdin);
    ___=R(),__=R(),n=R();
    for(int i=1;i<=n;i++)x[i]=R(),y[i]=R(),xx[i]=R(),yy[i]=R(),g.insert(i)
    ,a[x[i]].insert(P(y[i],i)),b[y[i]].insert(P(x[i],i))
    ,a[xx[i]].insert(P(yy[i],i)),b[yy[i]].insert(P(xx[i],i));
    for(int i=1;i<=___;i++)a[i].insert(P(__+1,n+1)),a[i].insert(P(0,n+2));
    for(int i=1;i<=__;i++)b[i].insert(P(___+1,n+3)),b[i].insert(P(0,n+4));
    int q,an=0;q=R();
    while(q--){
        int X,Y;char _,__;
        X=R(),Y=R();_=S(),__=S();
        if(chk(X,Y))continue;
        //printf("%d %d %d %d\n",X,Y,_,__);
        if(_=='L'||__=='L')B=A,A=a[X].lower_bound(P(Y,0)),A--;
        if(_=='R'||__=='R')B=A,A=a[X].lower_bound(P(Y,0))    ;
        if(_=='U'||__=='U')B=A,A=b[Y].lower_bound(P(X,0)),A--;
        if(_=='D'||__=='D')B=A,A=b[Y].lower_bound(P(X,0))    ;
        //if(X==2&&Y==4)A++;
        //printf("%d %d %d %d\n",X,Y,A->second,B->second);
        if(B->second==A->second){++an;int t=A->second;o[t]=1;
        //printf("%d %d\n",X,Y);
        if(_=='L'||__=='L')A=a[X].lower_bound(P(Y,0)),A--,b[A->first].erase(P(X,t)),a[X].erase(A);
        if(_=='R'||__=='R')A=a[X].lower_bound(P(Y,0))    ,b[A->first].erase(P(X,t)),a[X].erase(A);
        if(_=='U'||__=='U')A=b[Y].lower_bound(P(X,0)),A--,a[A->first].erase(P(Y,t)),b[Y].erase(A);
        if(_=='D'||__=='D')A=b[Y].lower_bound(P(X,0))    ,a[A->first].erase(P(Y,t)),b[Y].erase(A);
        }
    }printf("%d ",an);//return 0;
    int t=1;an=0;
    for(int i=1;i<=n;i++)if(o[i])a[x[i]].insert(P(y[i],i)),b[y[i]].insert(P(x[i],i)),
    a[xx[i]].insert(P(yy[i],i)),b[yy[i]].insert(P(xx[i],i));
    while(t){
        t=0;
        for(_=g.begin();_!=g.end();){
            int p=*_,pr=an;
            if(xx[p]==x[p]){
                if(check(x[p],(y[p]+yy[p])/2,p))cl(x[p],(y[p]+yy[p])/2,'L','R');
            }else
            if(yy[p]==y[p]){
                if(check((x[p]+xx[p])/2,y[p],p))cl((x[p]+xx[p])/2,y[p],'U','D');
            }else
            {
                if(check(x[p],yy[p],p))cl(x[p],yy[p],x[p]<xx[p]?'D':'U',y[p]<yy[p]?'L':'R');
                else
                if(check(xx[p],y[p],p))cl(xx[p],y[p],x[p]<xx[p]?'U':'D',y[p]<yy[p]?'R':'L');
            }++_;
            if(an-pr)g.erase(p),t++;
        }
    }printf("%d\n",an);
    for(int i=1;i<=an;i++)printf("%d %d %c %c\n",c[i],d[i],e[i],f[i]);
}
2017/2/20 19:43
加载中...