oj.uz

Submission #1041742

# Submission time Handle Problem Language Result Execution time Memory
1041742 2024-08-02T07:42:03 Z vjudge1 Tenis (COI19_tenis) C++17
30 / 100
 408 ms 33792 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 176 ms 28508 KB Output is correct
14 Correct 158 ms 29008 KB Output is correct
15 Correct 175 ms 29264 KB Output is correct
16 Correct 198 ms 29012 KB Output is correct
17 Correct 314 ms 30544 KB Output is correct
18 Correct 231 ms 30544 KB Output is correct
19 Correct 281 ms 30204 KB Output is correct
20 Correct 91 ms 26852 KB Output is correct
21 Correct 273 ms 30296 KB Output is correct
22 Correct 196 ms 29652 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 33792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 176 ms 28508 KB Output is correct
14 Correct 158 ms 29008 KB Output is correct
15 Correct 175 ms 29264 KB Output is correct
16 Correct 198 ms 29012 KB Output is correct
17 Correct 314 ms 30544 KB Output is correct
18 Correct 231 ms 30544 KB Output is correct
19 Correct 281 ms 30204 KB Output is correct
20 Correct 91 ms 26852 KB Output is correct
21 Correct 273 ms 30296 KB Output is correct
22 Correct 196 ms 29652 KB Output is correct
23 Incorrect 408 ms 33792 KB Output isn't correct
24 Halted 0 ms 0 KB -