oj.uz

Submission #1118668

# Submission time Handle Problem Language Result Execution time Memory
1118668 2024-11-26T01:40:33 Z vjudge1 Tenis (COI19_tenis) C++14
100 / 100
 149 ms 7856 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 360 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 2 ms 352 KB Output is correct
9 Correct 2 ms 352 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 500 KB Output is correct
12 Correct 1 ms 456 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 2 ms 352 KB Output is correct
9 Correct 2 ms 352 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 500 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 48 ms 6340 KB Output is correct
14 Correct 48 ms 6188 KB Output is correct
15 Correct 52 ms 6396 KB Output is correct
16 Correct 44 ms 6220 KB Output is correct
17 Correct 43 ms 6384 KB Output is correct
18 Correct 65 ms 6220 KB Output is correct
19 Correct 47 ms 6220 KB Output is correct
20 Correct 63 ms 6172 KB Output is correct
21 Correct 47 ms 6220 KB Output is correct
22 Correct 60 ms 6408 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 7316 KB Output is correct
2 Correct 99 ms 7248 KB Output is correct
3 Correct 67 ms 7356 KB Output is correct
4 Correct 65 ms 7372 KB Output is correct
5 Correct 72 ms 7328 KB Output is correct
6 Correct 64 ms 7368 KB Output is correct
7 Correct 87 ms 7360 KB Output is correct
8 Correct 69 ms 7340 KB Output is correct
9 Correct 81 ms 7460 KB Output is correct
10 Correct 70 ms 7244 KB Output is correct
11 Correct 68 ms 7252 KB Output is correct
12 Correct 101 ms 7244 KB Output is correct
13 Correct 106 ms 7244 KB Output is correct
14 Correct 63 ms 7332 KB Output is correct
15 Correct 66 ms 7256 KB Output is correct

Subtask #5
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 2 ms 352 KB Output is correct
9 Correct 2 ms 352 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 500 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 48 ms 6340 KB Output is correct
14 Correct 48 ms 6188 KB Output is correct
15 Correct 52 ms 6396 KB Output is correct
16 Correct 44 ms 6220 KB Output is correct
17 Correct 43 ms 6384 KB Output is correct
18 Correct 65 ms 6220 KB Output is correct
19 Correct 47 ms 6220 KB Output is correct
20 Correct 63 ms 6172 KB Output is correct
21 Correct 47 ms 6220 KB Output is correct
22 Correct 60 ms 6408 KB Output is correct
23 Correct 112 ms 7316 KB Output is correct
24 Correct 99 ms 7248 KB Output is correct
25 Correct 67 ms 7356 KB Output is correct
26 Correct 65 ms 7372 KB Output is correct
27 Correct 72 ms 7328 KB Output is correct
28 Correct 64 ms 7368 KB Output is correct
29 Correct 87 ms 7360 KB Output is correct
30 Correct 69 ms 7340 KB Output is correct
31 Correct 81 ms 7460 KB Output is correct
32 Correct 70 ms 7244 KB Output is correct
33 Correct 68 ms 7252 KB Output is correct
34 Correct 101 ms 7244 KB Output is correct
35 Correct 106 ms 7244 KB Output is correct
36 Correct 63 ms 7332 KB Output is correct
37 Correct 66 ms 7256 KB Output is correct
38 Correct 149 ms 7732 KB Output is correct
39 Correct 96 ms 7352 KB Output is correct
40 Correct 131 ms 7768 KB Output is correct
41 Correct 94 ms 7408 KB Output is correct
42 Correct 90 ms 7472 KB Output is correct
43 Correct 130 ms 7712 KB Output is correct
44 Correct 79 ms 7344 KB Output is correct
45 Correct 94 ms 7576 KB Output is correct
46 Correct 119 ms 7572 KB Output is correct
47 Correct 82 ms 7500 KB Output is correct
48 Correct 95 ms 7504 KB Output is correct
49 Correct 98 ms 7584 KB Output is correct
50 Correct 89 ms 7504 KB Output is correct
51 Correct 103 ms 7596 KB Output is correct
52 Correct 130 ms 7716 KB Output is correct
53 Correct 85 ms 7572 KB Output is correct
54 Correct 88 ms 7616 KB Output is correct
55 Correct 92 ms 7576 KB Output is correct
56 Correct 99 ms 7856 KB Output is correct
57 Correct 80 ms 7500 KB Output is correct
58 Correct 114 ms 7584 KB Output is correct