oj.uz

Submission #144199

# Submission time Handle Problem Language Result Execution time Memory
144199 2019-08-16T09:55:18 Z Abelyan Tenis (COI19_tenis) C++17
18 / 100
 500 ms 17160 KB 
#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];
int n,q,qan;
set<int> s[3],tarb[3][3];
set<int>::iterator it;
void ins(int ham,int val){
    s[ham].insert(val);
    FOR(i,3){
        if (ham==i)continue;
        it=tarb[i][ham].find(val);
        if (it==tarb[i][ham].end()){
            tarb[ham][i].insert(val);
            qan++;
        }
        else{
            tarb[i][ham].erase(it);
            qan--;
        }
    }
}



int get(){
    int pat=-1;
    qan=0;
    FOR(i,n-1){
        //cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<endl;
        ins(0,a[0][i]);
        ins(1,a[1][i]);
        ins(2,a[2][i]);
        //cout<<qan<<" ";
        if (!qan)pat=i;
    }
    //cout<<endl;
    FOR(i,3){
        s[i].clear();
        FOR(j,3){
            tarb[i][j].clear();
        }
    }
    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 500 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 8 ms 504 KB Output is correct
12 Correct 9 ms 504 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 500 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 8 ms 504 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Execution timed out 1059 ms 16696 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 612 ms 17160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 500 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 8 ms 504 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Execution timed out 1059 ms 16696 KB Time limit exceeded
14 Halted 0 ms 0 KB -