Submission #1118668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118668		vjudge1	Tenis (COI19_tenis)	C++14	100 / 100	149 ms	7856 KiB

tenis

#include<cstdio>
#include<cstring>
#include<algorithm>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

const int NV=1e5;

namespace seg{
    struct SEGN{
        int v,p,tad;
    } tr[NV*4+5];
    void doadd(int x,int z){
        tr[x].v+=z;
        tr[x].tad+=z;
    }void dn(int x){
        if(tr[x].tad){
            doadd(x*2,tr[x].tad);
            doadd(x*2+1,tr[x].tad);
            tr[x].tad=0;
        }
    }void up(int x){
        tr[x].v=max(tr[x*2].v,tr[x*2+1].v);
        if(tr[x*2].v>=tr[x*2+1].v) tr[x].p=tr[x*2].p;
        else tr[x].p=tr[x*2+1].p;
    }void upd(int x,int l,int r,int p,int z){
        if(p<=l){
            doadd(x,z);
            return;
        }
        int mid=l+r>>1;
        dn(x);
        if(p<=mid) upd(x*2,l,mid,p,z);
        upd(x*2+1,mid+1,r,p,z);
        up(x);
    }void build(int x,int l,int r){
        if(l==r) tr[x]={-l,l};
        else{
            int mid=l+r>>1;
            build(x*2,l,mid);
            build(x*2+1,mid+1,r);
            up(x);
        }
    }
}

namespace xm{
    int pos[3][NV+5];
    void _(){
        int N,Q;

        scanf("%d%d",&N,&Q);
        for(int t=0;t<3;++t)
        for(int i=1;i<=N;++i){
            int x;
            scanf("%d",&x);
            pos[t][x]=i;
        }
        seg::build(1,1,N);
        for(int i=1;i<=N;++i) seg::upd(1,1,N,max({pos[0][i],pos[1][i],pos[2][i]}),1);
        //printf("%d %d\n",seg::tr[1].v,seg::tr[1].p);
        while(Q--){
            int op,x;
            scanf("%d%d",&op,&x);
            if(op==1) puts(seg::tr[1].p>=max({pos[0][x],pos[1][x],pos[2][x]})?"DA":"NE");
            else{
                int t=x;
                int y;
                scanf("%d%d",&x,&y);
                seg::upd(1,1,N,max({pos[0][x],pos[1][x],pos[2][x]}),-1);
                seg::upd(1,1,N,max({pos[0][y],pos[1][y],pos[2][y]}),-1);
                --t;
                std::swap(pos[t][x],pos[t][y]);
                //for(int t=0;t<3;++t,puts("")) for(int i=1;i<=N;++i) printf("%d ",pos[t][i]);
                seg::upd(1,1,N,max({pos[0][x],pos[1][x],pos[2][x]}),1);
                seg::upd(1,1,N,max({pos[0][y],pos[1][y],pos[2][y]}),1);
                //printf("%d %d %d %d\n",max({pos[0][x],pos[1][x],pos[2][x]}),max({pos[0][y],pos[1][y],pos[2][y]}),seg::tr[1].v,seg::tr[1].p);
            }
        }
    }
}

int main(){
    //freopen("tennis.in","r",stdin);
    //freopen("tennis.out","w",stdout);
    xm::_();
    return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'void seg::upd(int, int, int, int, int)':
tenis.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int mid=l+r>>1;
      |                 ~^~
tenis.cpp: In function 'void seg::build(int, int, int)':
tenis.cpp:46:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int mid=l+r>>1;
      |                     ~^~
tenis.cpp: In function 'void xm::_()':
tenis.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d%d",&N,&Q);
      |         ~~~~~^~~~~~~~~~~~~~
tenis.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
tenis.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             scanf("%d%d",&op,&x);
      |             ~~~~~^~~~~~~~~~~~~~~
tenis.cpp:76:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |                 scanf("%d%d",&x,&y);
      |                 ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49