Submission #548565

#	Time	Username	Problem	Language	Result	Execution time	Memory
548565		leaked	Tenis (COI19_tenis)	C++17	100 / 100	190 ms	8200 KiB

tenis

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
//#define int long long
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e5+1;
int t[4*N],p[4*N];
void push(int v,int tl,int tr){
    if(tl==tr||!p[v])
        return;
    for(auto &u : {2*v,2*v+1})
        p[u]+=p[v],t[u]+=p[v];
    p[v]=0;
}
void add(int l,int r,int x,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
        t[v]+=x;p[v]+=x;
        return;
    }
    if(tl>r||tr<l)
        return;
    int tm=(tl+tr)>>1;push(v,tl,tr);
    add(l,r,x,2*v,tl,tm);add(l,r,x,2*v+1,tm+1,tr);
    t[v]=min(t[2*v],t[2*v+1]);
}
int get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r)
        return t[v];
    if(tl>r||tr<l)
        return 1e9;
    int tm=(tl+tr)>>1;push(v,tl,tr);
    return min(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
signed main(){
    fast_prep;
    int n,q;
    cin>>n>>q;
    vec<vec<int>>p(3,vec<int>(n));
    vec<vec<int>>ord(3,vec<int>(n));
    for(int i=0;i<3;i++){
        for(auto &z : p[i])
            cin>>z,--z;
        for(int j=0;j<n;j++) ord[i][p[i][j]]=j;
    }
    for(int i=0;i<n;i++) add(0,i,1,1,0,n-1);
    auto eval=[&](int i){
        return min({ord[0][i],ord[1][i],ord[2][i]});
    };
    for(int i=0;i<n;i++){
        add(0,eval(i),-1,1,0,n-1);
    }
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int x;
            cin>>x;
            --x;
            int j=eval(x);
            cout<<(get(1,j,1,0,n-1)==0?"NE":"DA")<<'\n';
        }
        else{
            int k,i,j;
            cin>>k>>i>>j;--i;--j;--k;
            add(0,eval(i),1,1,0,n-1);add(0,eval(j),1,1,0,n-1);
            swap(ord[k][i],ord[k][j]);
            add(0,eval(i),-1,1,0,n-1);add(0,eval(j),-1,1,0,n-1);

        }
    }
    return 0;
}
/*
abbaaa
cbbbbccbbccbbbbbbc
(((((((()))())))))

*/

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