oj.uz

답안 #752415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752415 2023-06-03T02:39:31 Z Username4132 Tenis (COI19_tenis) C++14
39 / 100
 118 ms 6220 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=100010, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 80 ms 5048 KB Output is correct
14 Correct 81 ms 5136 KB Output is correct
15 Correct 71 ms 5044 KB Output is correct
16 Correct 90 ms 5100 KB Output is correct
17 Correct 63 ms 5076 KB Output is correct
18 Incorrect 60 ms 5064 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 6136 KB Output is correct
2 Correct 102 ms 6092 KB Output is correct
3 Correct 118 ms 6132 KB Output is correct
4 Correct 89 ms 6072 KB Output is correct
5 Correct 96 ms 6080 KB Output is correct
6 Correct 94 ms 6080 KB Output is correct
7 Correct 115 ms 6220 KB Output is correct
8 Correct 84 ms 6084 KB Output is correct
9 Correct 109 ms 6076 KB Output is correct
10 Correct 95 ms 6120 KB Output is correct
11 Correct 100 ms 6124 KB Output is correct
12 Correct 97 ms 6052 KB Output is correct
13 Correct 99 ms 6092 KB Output is correct
14 Correct 95 ms 6196 KB Output is correct
15 Correct 102 ms 6152 KB Output is correct

Subtask #5
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 80 ms 5048 KB Output is correct
14 Correct 81 ms 5136 KB Output is correct
15 Correct 71 ms 5044 KB Output is correct
16 Correct 90 ms 5100 KB Output is correct
17 Correct 63 ms 5076 KB Output is correct
18 Incorrect 60 ms 5064 KB Output isn't correct
19 Halted 0 ms 0 KB -