Submission #752747

#	Time	Username	Problem	Language	Result	Execution time	Memory
752747		Username4132	Tenis (COI19_tenis)	C++14	100 / 100	227 ms	6592 KiB

tenis

#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+1][a[j]], -1);
                    sim_add(inv[0][a[j]], inv[k+1][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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49