Submission #676416

#	Time	Username	Problem	Language	Result	Execution time	Memory
676416		ziduo	Tenis (COI19_tenis)	C++14	100 / 100	174 ms	13480 KiB

tenis

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second

const ll MOD = 1e9+7;
int seg[400000][3];
void updateT(int x, int l, int r, int p, int v){
    if(l==r){
        seg[x][0]+=v;
        seg[x][1]=seg[x][0];
        seg[x][2]=p;
    }
    else{
        int s1=2*x, s2=2*x+1;
        int m = (l+r)/2;
        if(p<=m)updateT(s1, l, m, p, v);
        else updateT(s2, m+1, r, p, v);
        if(seg[s1][1]<=seg[s1][0]+seg[s2][1]){
            seg[x][1]=seg[s1][1];
            seg[x][2]=seg[s1][2];
        }
        else{
            seg[x][1]=seg[s1][0]+seg[s2][1];
            seg[x][2]=seg[s2][2];            
        }
        seg[x][0]=seg[s1][0]+seg[s2][0];
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, v, t;
    cin>>n>>q;
    vector<int> arr[n];
    int pos[n][3];
    for(int i=0; i<3; i++){
        for(int j=0; j<n; j++){
            cin>>v;
            v--;
            arr[v].push_back(j);
            pos[v][i]=j;
        }
    }
    int sum[n];
    memset(sum, -1, sizeof(sum));
    for(int i=0; i<n; i++){
        sort(arr[i].begin(), arr[i].end());
        sum[arr[i][0]]++;
    }
    for(int i=0; i<n; i++)updateT(1, 0, n-1, i, sum[i]);
    for(int i=0; i<q; i++){
        cin>>t;
        if(t==1){
            cin>>v;
            v--;
            if(arr[v][0]<=seg[1][2])cout<<"DA\n";
            else cout<<"NE\n";
        }
        else{
            int f, v1, v2;
            cin>>f>>v1>>v2;
            f--;
            v1--;
            v2--;
            updateT(1, 0, n-1, arr[v1][0], -1);
            updateT(1, 0, n-1, arr[v2][0], -1);
            int r = pos[v1][f];
            for(int j=0; j<3; j++)if(arr[v1][j]==r){
                arr[v1].erase(arr[v1].begin()+j);
                break;
            }
            arr[v1].push_back(pos[v2][f]);
            r=pos[v2][f];
            for(int j=0; j<3; j++)if(arr[v2][j]==r){
                arr[v2].erase(arr[v2].begin()+j);
                break;
            }
            arr[v2].push_back(pos[v1][f]);     
            swap(pos[v1][f], pos[v2][f]);
            sort(arr[v1].begin(), arr[v1].end());
            sort(arr[v2].begin(), arr[v2].end());
            updateT(1, 0, n-1, arr[v1][0], 1);
            updateT(1, 0, n-1, arr[v2][0], 1);
        }
    }
    
    return 0;
}

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