제출 #650227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650227		czhang2718	Tenis (COI19_tenis)	C++17	100 / 100	182 ms	7824 KiB

tenis

#include "bits/stdc++.h"
using namespace std;

const int N=1e5;
int n, q;
int p[3][N];
int ind[3][N];
int mn[4*N];
int lazy[4*N];

void push(int x, int lx, int rx){
    if(rx-lx==1 || !lazy[x]) return;
    mn[2*x+1]+=lazy[x];
    mn[2*x+2]+=lazy[x];
    lazy[2*x+1]+=lazy[x];
    lazy[2*x+2]+=lazy[x];
    lazy[x]=0;
}

void upd(int i, int v, int x, int lx, int rx){
    push(x, lx, rx);
    if(rx<=i) return;
    if(lx>=i){
        mn[x]+=v;
        lazy[x]+=v;
        return;
    }
    int m=(lx+rx)/2;
    upd(i, v, 2*x+1, lx, m);
    upd(i, v, 2*x+2, m, rx);
    mn[x]=min(mn[2*x+1], mn[2*x+2]);
}

void upd(int i, int v){
    upd(i, v, 0, 0, n);
}

int walk(int x, int lx, int rx){
    push(x, lx, rx);
    if(rx-lx==1) return lx;
    int m=(lx+rx)/2;
    if(mn[2*x+1]==0) return walk(2*x+1, lx, m);
    else return walk(2*x+2, m, rx);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;
    for(int j=0; j<3; j++){
        for(int i=0; i<n; i++){
            cin >> p[j][i];
            p[j][i]--;
            ind[j][p[j][i]]=i;
        }
    }

    for(int i=0; i<n; i++){
        upd(i, 1);
        upd(max({ind[0][i], ind[1][i], ind[2][i]}), -1);
    }

    while(q--){
        int op; cin >> op;
        if(op==1){
            int i; cin >> i;
            --i;
            int r=walk(0, 0, n);
            // cout << "walk " << r << '\n';
            if(max({ind[0][i], ind[1][i], ind[2][i]})<=r) cout << "DA\n";
            else cout << "NE\n";
        }
        else{
            int t, i,j; cin >> t >> i >> j;
            --t, --i, --j;
            upd(max({ind[0][i], ind[1][i], ind[2][i]}), 1);
            upd(max({ind[0][j], ind[1][j], ind[2][j]}), 1);
            swap(ind[t][i], ind[t][j]);
            upd(max({ind[0][i], ind[1][i], ind[2][i]}), -1);
            upd(max({ind[0][j], ind[1][j], ind[2][j]}), -1);
        }
    }
}

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