Submission #144206

#	Time	Username	Problem	Language	Result	Execution time	Memory
144206		Abelyan	Tenis (COI19_tenis)	C++17	51 / 100	1073 ms	3500 KiB

tenis

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=1e5+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

void yes(){
    cout<<"DA"<<endl;
}
void no(){
    cout<<"NE"<<endl;
}
/*
struct node{
    set<int> s[3],tarb[3][3];
    int qan;
    node(){qan=0;}
};

set<int>::iterator it;
node sg[4*N];



void ad(int v,int tl,int tr,int ind,int ham,int val){
    sg[v].s[ham].insert(val);
    FOR(i,3){
        if (ham==i)continue;
        it=sg[v].tarb[i][ham].find(val);
        if (it==sg[v].tarb[i][ham].end()){
            sg[v].tarb[ham][i].insert(val);
            sg[v].qan++;
        }
        else{
            sg[v].tarb[i][ham].erase(it);
            sg[v].qan--;
        }
    }
    if (tl==tr)return;
    int tm=(tl+tr)/2;
    if (ind<=tm)ad(v+v,tl,tm,ind,ham,val);
    else ad(v+v+1,tm+1,tr,ind,ham,val);
}

void rem(int v,int tl,int tr,int ind,int ham,int val){
    sg[v].s[ham].erase(val);
    FOR(i,3){
        if (ham==i)continue;
        it=sg[v].tarb[ham][i].find(val);
        if (it!=sg[v].tarb[ham][i].end()){
            sg[v].tarb[ham][i].erase(it);
            sg[v].qan--;
        }
        else{
            sg[v].tarb[i][ham].insert(val);
            sg[v].qan++;
        }
    }
    if (tl==tr)return;
    int tm=(tl+tr)/2;
    if (ind<=tm)rem(v+v,tl,tm,ind,ham,val);
    else rem(v+v+1,tm+1,tr,ind,ham,val);
}

int n,q;
int query(int v,int tl,int tr){
    if (sg[v].qan==0 && tr!=n-1) return tr-tl+1;
    if (tl==tr)return -1;
    int tm=(tl+tr)/2;
    int ans=query(v+v,tl,tm);
    if (query(v+v,tl,tm)==tm-tl+1){
        return tm-tl+1+query(v+v+1,tm+1,tr);
    }
    return ans;
}
*/
int a[3][N],ind[3][N],col[N];
int n,q,qan;


int get(){
    int pat=-1;
    qan=0;
    FOR(i,n-1){
        //cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<endl;
        col[a[0][i]]++;
        if (col[a[0][i]]==1 )qan++;
        if (col[a[0][i]]==3)qan--;
        col[a[1][i]]++;
        if (col[a[1][i]]==1)qan++;
        if (col[a[1][i]]==3)qan--;
        col[a[2][i]]++;
        if (col[a[2][i]]==1)qan++;
        if (col[a[2][i]]==3)qan--;
        //cout<<qan<<" ";
        if (!qan)pat=i;
    }
    FORT(i,1,n)col[i]=0;
    return pat;
}

int main(){
    fastio;
    srng;
    cin>>n>>q;
    FOR(i,3)
        FORD(j,n){

            cin>>a[i][j];
            //ad(1,0,n-1,j,i,a[i][j]);
            ind[i][a[i][j]]=j;
        }
    int pat=get();
    //cout<<pat<<endl;
    FOR(i,q){
        int tp;
        cin>>tp;
        if (tp==1){
            int x;
            cin>>x;
            //cout<<query(1,0,n-1)<<endl;
            if (ind[0][x]<=pat)no();
            else yes();
        }
        else{
            int tp,v,u;
            cin>>tp>>v>>u;
            tp--;
            /*
            int indv=ind[tp][v];
            int indu=ind[tp][u];

            rem(1,0,n-1,indv,tp,v);
            ad(1,0,n-1,indv,tp,u);
            rem(1,0,n-1,indu,tp,u);
            ad(1,0,n-1,indu,tp,v);
            */
            swap(ind[tp][v],ind[tp][u]);
            a[tp][ind[tp][v]]=v;
            a[tp][ind[tp][u]]=u;
            pat=get();
            //cout<<pat<<endl;

        }
    }
    return 0;
}
/*
7 2 8
C 1
C 2
C 3
C 4
C 5
C 6
O 7
O 7

*/

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