oj.uz

Submission #752746

# Submission time Handle Problem Language Result Execution time Memory
752746 2023-06-03T15:16:04 Z Username4132 Tenis (COI19_tenis) C++14
39 / 100
 107 ms 6224 KB 
#include<iostream>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforsn(i, s, n) for(int i=n-1; i>=(int)s; --i)
#define F first
#define S second

const int MAXN=200010, INF=1000000000;
int n, q, he, lazy[MAXN], inv[3][MAXN];
pii tr[2*MAXN];

void apply(int p, int value){
    if(p<n) lazy[p]+=value;
    tr[p].F+=value;
}

void build(int p){
    while(p>1) p>>=1, tr[p]=min(tr[p<<1], tr[p<<1|1]), tr[p].F+=lazy[p];
}

void push(int p){
    for(int s=he; s>0; --s){
        int i=p>>s;
        if(lazy[i]){
            apply(i<<1, lazy[i]);
            apply(i<<1|1, lazy[i]);
            lazy[i]=0;
        }
    }
}

void inc(int l, int r, int value){
    l+=n, r+=n;
    int l0=l, r0=r;
    for(; l<r; l>>=1, r>>=1){
        if(l&1) apply(l++, value);
        if(r&1) apply(--r, value);
    }
    build(l0);
    build(r0-1);
}

pii query(int l, int r){
    pii ret = {INF, INF};
    l+=n, r+=n;
    push(l);
    push(r-1);
    for(; l<r; l>>=1, r>>=1){
        if(l&1) ret=min(tr[l++], ret);
        if(r&1) ret=min(ret, tr[--r]);
    }
    return ret;
}

void sim_add(int l, int r, int value){
    if(l>=r) swap(l, r);
    inc(l, r, value);
}

int main(){
    scanf("%d %d", &n, &q);
    he = 8*sizeof(int) - __builtin_clz(n);
    forn(i, n) tr[n+i].S=i;
    dforsn(i, 1, n) tr[i]=min(tr[i<<1], tr[i<<1|1]);
    forn(i, 3) forn(j, n){
        int a; scanf("%d", &a), --a;
        inv[i][a]=j;
    }
    forn(j, 2) forn(i, n) sim_add(inv[0][i], inv[j+1][i], 1);
    forn(i, q){
        int type; scanf("%d", &type);
        if(type==1){
            int x; scanf("%d", &x), --x;
            int bnd = query(0, n).S;
            printf(inv[0][x]<=bnd? "DA\n" : "NE\n");
        }
        else{
            int p, a[2]; scanf("%d %d %d", &p, a, a+1), --p, --a[0], --a[1];
            if(p==0){
                forn(j, 2) forn(k, 2){
                    sim_add(inv[0][a[j]], inv[k][a[j]], -1);
                    sim_add(inv[0][a[j]], inv[k][a[j^1]], 1);
                }
            }
            else{
                forn(j, 2){
                    sim_add(inv[0][a[j]], inv[p][a[j]], -1);
                    sim_add(inv[0][a[j]], inv[p][a[j^1]], 1);
                }
            }
            swap(inv[p][a[0]], inv[p][a[1]]);
        }
    }
}

Compilation message

tenis.cpp: In function 'int main()':
tenis.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tenis.cpp:67:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         int a; scanf("%d", &a), --a;
      |                ~~~~~^~~~~~~~~~
tenis.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         int type; scanf("%d", &type);
      |                   ~~~~~^~~~~~~~~~~~~
tenis.cpp:74:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |             int x; scanf("%d", &x), --x;
      |                    ~~~~~^~~~~~~~~~
tenis.cpp:79:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |             int p, a[2]; scanf("%d %d %d", &p, a, a+1), --p, --a[0], --a[1];
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 77 ms 5132 KB Output is correct
14 Correct 81 ms 5152 KB Output is correct
15 Correct 82 ms 5112 KB Output is correct
16 Correct 74 ms 5108 KB Output is correct
17 Correct 57 ms 5068 KB Output is correct
18 Incorrect 58 ms 5108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6224 KB Output is correct
2 Correct 106 ms 6192 KB Output is correct
3 Correct 102 ms 6112 KB Output is correct
4 Correct 88 ms 6084 KB Output is correct
5 Correct 101 ms 6156 KB Output is correct
6 Correct 99 ms 6088 KB Output is correct
7 Correct 96 ms 6216 KB Output is correct
8 Correct 87 ms 6180 KB Output is correct
9 Correct 102 ms 6096 KB Output is correct
10 Correct 96 ms 6064 KB Output is correct
11 Correct 102 ms 6216 KB Output is correct
12 Correct 102 ms 6196 KB Output is correct
13 Correct 103 ms 6220 KB Output is correct
14 Correct 103 ms 6092 KB Output is correct
15 Correct 103 ms 6092 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 77 ms 5132 KB Output is correct
14 Correct 81 ms 5152 KB Output is correct
15 Correct 82 ms 5112 KB Output is correct
16 Correct 74 ms 5108 KB Output is correct
17 Correct 57 ms 5068 KB Output is correct
18 Incorrect 58 ms 5108 KB Output isn't correct
19 Halted 0 ms 0 KB -