Submission #777877

#	Time	Username	Problem	Language	Result	Execution time	Memory
777877		Ahmed57	Tenis (COI19_tenis)	C++17	100 / 100	143 ms	6612 KiB

tenis

#include <bits/stdc++.h>

using namespace std;
int seg[400001];
int lazy[400001];
void prop(int p,int l,int r){
    seg[p]+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void build(int p,int l,int r){
    if(l==r){
        seg[p] = l;
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int lq,int rq,int val){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=val;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);update(p*2+1,md+1,r,lq,rq,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r){
    if(l==r){
        return l;
    }
    int md = (l+r)/2;
    prop(p*2,l,md);prop(p*2+1,md+1,r);
    if(seg[p*2]==0)return query(p*2,l,md);
    else return query(p*2+1,md+1,r);
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    int arr1[n+1],arr2[n+1],arr3[n+1];
    int ind1[n+1],ind2[n+1],ind3[n+1];
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        ind1[x] = i;
    }for(int i = 1;i<=n;i++){
        int x;cin>>x;
        ind2[x] = i;
    }for(int i = 1;i<=n;i++){
        int x;cin>>x;
        ind3[x] = i;
    }
    build(1,1,n);
    for(int i = 1;i<=n;i++){
        update(1,1,n,max({ind1[i],ind2[i],ind3[i]}),n,-1);
    }
    while(q--){
        int ty;cin>>ty;
        if(ty==1){
            int x;cin>>x;
            prop(1,1,n);
            if(max({ind1[x],ind2[x],ind3[x]})<=query(1,1,n)){
                cout<<"DA\n";
            }else cout<<"NE\n";
        }else{
            int p,a,b;cin>>p>>a>>b;
            update(1,1,n,max({ind1[a],ind2[a],ind3[a]}),n,1);
            update(1,1,n,max({ind1[b],ind2[b],ind3[b]}),n,1);
            if(p==1)swap(ind1[a],ind1[b]);
            if(p==2)swap(ind2[a],ind2[b]);
            if(p==3)swap(ind3[a],ind3[b]);
            update(1,1,n,max({ind1[a],ind2[a],ind3[a]}),n,-1);
            update(1,1,n,max({ind1[b],ind2[b],ind3[b]}),n,-1);
        }
    }
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:48:9: warning: unused variable 'arr1' [-Wunused-variable]
   48 |     int arr1[n+1],arr2[n+1],arr3[n+1];
      |         ^~~~
tenis.cpp:48:19: warning: unused variable 'arr2' [-Wunused-variable]
   48 |     int arr1[n+1],arr2[n+1],arr3[n+1];
      |                   ^~~~
tenis.cpp:48:29: warning: unused variable 'arr3' [-Wunused-variable]
   48 |     int arr1[n+1],arr2[n+1],arr3[n+1];
      |                             ^~~~

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