Submission #1041742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041742		vjudge1	Tenis (COI19_tenis)	C++17	30 / 100	408 ms	33792 KiB

tenis

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
#define int long long 
const int N = 100001;
const int mod = 1e9+7;
const int mod1 = 998244353;
map<int,multiset<int>> g;
vector<bool> vis(N);
void dfs(int node){
    if(vis[node])return;
    vis[node] = true;
    for(int child:g[node]){
        dfs(child);
    }
}
void solve(){
    int n,q;cin >> n>> q;
    int a[n+1][4];
    for(int i = 1;i<=n ; i++)
        cin >> a[i][1];
    for(int i = 1;i<=n ;i ++)
        cin >> a[i][2];
    for(int i = 1;i<=n ;i ++)
        cin >> a[i][3];
    vector<vector<int>> queries;bool f= true;
    for(int i = 0 ;i <q ;i ++){
        int t;cin >> t;
        if(t == 1){
            int x;
            cin >> x;
            queries.push_back({1,x});
        }
        else{
            int P,A,B;
            cin >> P >> A >> B;f=false;
            queries.push_back({2,P,A,B});
        }
    }
    if(f){
        //all queries are of type 1;
        map<int,int> m1;
        map<int,int> m2;
        map<int,int> m3;
        for(int i = 1;i<= n; i++){
            m1[a[i][1]] = i;
        }
        for(int i = 1 ;i <=n ;i ++){
            m2[a[i][2]] = i;
        }
        for(int i = 1;i<=n ;i ++){
            m3[a[i][3]] = i;
        }
        vector<int> mx(n);
        for(int i = 1;i<=n ;i ++)
            for(int j = 1 ;j <=3 ;j ++)
                mx[a[i][j]-1] = max(mx[a[i][j]-1],i);
        int t[n+1][3][2];
        t[n][0][0] = m2[a[n][1]];
        t[n][0][1] = m3[a[n][1]];
        t[n][1][0] = m1[a[n][2]];
        t[n][1][1] = m3[a[n][2]];
        t[n][2][0] = m1[a[n][3]];
        t[n][2][1] = m2[a[n][3]];
        for(int i = n-1;i>=1 ;i --){
            t[i][0][0] = min(t[i-1][0][0],m2[a[i][1]]);
            t[i][0][1] = min(t[i-1][0][1],m3[a[i][1]]);
            t[i][1][0] = min(t[i-1][1][0],m1[a[i][2]]);
            t[i][1][1] = min(t[i-1][1][1],m3[a[i][2]]);
            t[i][2][0] = min(t[i-1][2][0],m1[a[i][3]]);
            t[i][2][1] = min(t[i-1][2][1],m2[a[i][3]]);
        }
        sort(mx.begin(),mx.end());
        vector<bool> ans(n+1);
        for(int i = n;i>=1; i--){
            int first = min(m1[a[i][1]],min(t[i][1][0],t[i][2][0]));
            int second = min({m2[a[i][1]],t[i][0][0],t[i][2][1]});
            int third = min({m3[a[i][1]],t[i][0][1],t[i][1][1]});

            if(mx[0]>=min({first,second,third})){
                ans[a[i][1]] = true;
            }
        }
        for(int i = 0;i<q ;i ++){
            int x = queries[i][1];
            if(ans[x]){cout<<"DA"<<endl;}
            else cout<<"NE"<<endl;
        }
    }
    else{
         for(int i = 2; i<=n ;i ++){
        g[a[i-1][1]].insert(a[i][1]);
        g[a[i-1][2]].insert(a[i][2]);
        g[a[i-1][3]].insert(a[i][3]);
    }
    for(int its = 0 ;its <q ;its ++){
        int it = queries[its][0];
        if(it == 1){
            int X = queries[its][1];
            for(int i = 1;i<=n ;i++)vis[i] =false;
            dfs(X);bool f= true;
            for(int i = 1;i<=n ; i++){
                if(!vis[i])f=false;
            }
            if(f)cout<<"DA"<<endl;
            else cout<<"NE"<<endl;
        }
        else{
            int P = queries[its][1];
            int A = queries[its][2];
            int B = queries[its][3];
            int first_pos = -1;
            int second_pos = -1;
            for(int i = 1;i<=n ;i ++){
                if(a[i][P] == A)first_pos = i;
                if(a[i][P] == B)second_pos = i;
            }
            if(first_pos>1){
                auto itt = g[a[first_pos-1][P]].find(a[first_pos][P]);
                if(itt!=g[a[first_pos-1][P]].end())g[a[first_pos-1][P]].erase(itt);
            }
            if(first_pos<n){
                auto itt = g[a[first_pos][P]].find(a[first_pos+1][P]);
                if(itt!=g[a[first_pos][P]].end())g[a[first_pos][P]].erase(itt);
            }
            if(second_pos>1){
                auto itt = g[a[second_pos-1][P]].find(a[second_pos][P]);
                if(itt!=g[a[second_pos-1][P]].end())g[a[second_pos-1][P]].erase(itt);
            }
            if(second_pos<n){
                auto itt = g[a[second_pos][P]].find(a[second_pos+1][P]);
                if(itt!=g[a[second_pos][P]].end())g[a[second_pos][P]].erase(itt);
            }
            swap(a[first_pos][P],a[second_pos][P]);
            if(first_pos>1){
                g[a[first_pos-1][P]].insert(a[first_pos][P]);
            }
            if(first_pos<n){
                g[a[first_pos][P]].insert(a[first_pos+1][P]);
            }
            if(second_pos>1){
                g[a[second_pos-1][P]].insert(a[second_pos][P]);
            }
            if(second_pos<n){
                g[a[second_pos][P]].insert(a[second_pos+1][P]);
            }
        }

    }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    
    int t=1;
    // cin>>t;
    cout<<setprecision(16);
    while(t--){
        solve();
    }
}

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