Submission #254344

#	Time	Username	Problem	Language	Result	Execution time	Memory
254344		amiratou	Tenis (COI19_tenis)	C++14	100 / 100	300 ms	32672 KiB

tenis

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int tab[3][100005],A[100005],st[400005],lazy[400005],pos[100005][3],arr[100005],n;
multiset<int,greater<int> > lst[100005];
void build(int node,int l,int r){
    if(l==r){
        st[node]=A[l];
        return;
    }
    int med=(l+r)>>1;
    build(node*2,l,med),build(node*2+1,med+1,r);
    st[node]=min(st[node*2],st[node*2+1]);
}
void prop(int node,int l,int r){
    if(lazy[node]){
        st[node]+=lazy[node];
        if(l!=r){
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
}
void update(int node,int l,int r,int i,int j,int val){
    prop(node,l,r);
    if(l>j||r<i)
        return;
    if(l>=i && r<=j){
        st[node]+=val;
        if(l!=r){
            lazy[node*2]+=val;
            lazy[node*2+1]+=val;
        }
        return ;
    }
    int med=(l+r)>>1;
    update(node*2,l,med,i,j,val),update(node*2+1,med+1,r,i,j,val);
    st[node]=min(st[node*2],st[node*2+1]);
}
int query(int node,int l,int r,int i){
    prop(node,l,r);
    if(l>i ||r<i)
        return INF;
    if(l==r)
        return st[node];
    int med=(l+r)>>1;
    return min(query(node*2,l,med,i),query(node*2+1,med+1,r,i));
}
void update(int t,int a,int b){
    update(1,0,n-1,*lst[b].begin(),n-1,1);
    update(1,0,n-1,*lst[a].begin(),n-1,1);
    lst[a].erase(lst[a].find(pos[a][t]));
    lst[b].erase(lst[b].find(pos[b][t]));
    swap(pos[a][t],pos[b][t]);
    lst[a].insert(pos[a][t]);
    lst[b].insert(pos[b][t]);
    update(1,0,n-1,*lst[b].begin(),n-1,-1);
    update(1,0,n-1,*lst[a].begin(),n-1,-1);
    
}
bool query(int x){
    int l=0,r=n-1,node=1;
    prop(node,l,r);
    while(l!=r){
        int med=(l+r)>>1;
        prop(node*2,l,med),prop(node*2+1,med+1,r);
        if(!st[node*2])r=med,node*=2;
        else l=med+1,node=node*2+1;
    }
    return (l>=(*lst[x].begin()));
}
int32_t main(){
    boost;
    //freopen(".in","r",stdin);
    int q,cnt=1,t,x,a,b;
    cin>>n>>q;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < n; ++j)
            cin>>tab[i][j],lst[tab[i][j]].insert(j),pos[tab[i][j]][i]=j;
    for (int i = 1; i <= n; ++i)
        arr[*lst[i].begin()]--;
    for (int i = 0; i < n; ++i)
    {
        if(i)arr[i]+=arr[i-1];
        A[i]=cnt+arr[i];
        cnt++;
    }
    build(1,0,n-1);
    while(q--){
        cin>>t;
        if(t==1){
            cin>>x;
            if(query(x))cout<<"DA\n";
            else cout<<"NE\n";
        }
        else{
            cin>>x>>a>>b;
            x--;
            update(x,a,b);
        }
    }
    return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

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