Submission #364534

#	Time	Username	Problem	Language	Result	Execution time	Memory
364534		FatihSolak	Tenis (COI19_tenis)	C++17	100 / 100	453 ms	7308 KiB

tenis

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int t[4*N],lazy[4*N];
int pos[N][4];
void push(int v){
    t[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}
void upd(int v,int tl,int tr,int l,int r,int val){
    if(tr < l || r < tl)return;
    if(l <= tl && tr <= r){
        t[v]+=val;
        lazy[v]+=val;
        return;
    }
    push(v);
    int tm = (tl+tr)/2;
    upd(v*2,tl,tm,l,r,val);
    upd(v*2+1,tm+1,tr,l,r,val);
    t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
    if(tr < l || r < tl)return 1e9;
    if(l <= tr && tr <= r){
        return t[v];
    }
    push(v);
    int tm = (tl+tr)/2;
    return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void solve(){
    int n,q;
    cin >> n >> q;
    for(int i=1;i<4;i++){
        for(int j=1;j<=n;j++){
            int a;
            cin >> a;
            pos[a][i] = j;
        }
    }
    for(int i=1;i<=n;i++){
        upd(1,1,n,i,i,i);
        upd(1,1,n,max({pos[i][1],pos[i][2],pos[i][3]}),n,-1);
    }
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int x;
            cin >> x;
            cout << (get(1,1,n,1,max({pos[x][1],pos[x][2],pos[x][3]})-1) == 0?"NE":"DA") << endl;
        }
        if(type == 2){
            int p,x,y;
            cin >> p >> x >> y;
            upd(1,1,n,max({pos[x][1],pos[x][2],pos[x][3]}),n,1);
            upd(1,1,n,max({pos[y][1],pos[y][2],pos[y][3]}),n,1);
            swap(pos[x][p],pos[y][p]);
            upd(1,1,n,max({pos[x][1],pos[x][2],pos[x][3]}),n,-1);
            upd(1,1,n,max({pos[y][1],pos[y][2],pos[y][3]}),n,-1);
        }
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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