Submission #467799

#	Time	Username	Problem	Language	Result	Execution time	Memory
467799		couplefire	Tenis (COI19_tenis)	C++17	100 / 100	154 ms	7732 KiB

tenis

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

const int N = 1<<17;

struct node{ll sum = 0, psum = 0;} tree[N<<1];
int n, q, pos[3][N];

void upd(int pos, int val, int v = 1, int tl = 0, int tr = N-1){
    if(tl==tr){
        tree[v].sum = val;
        tree[v].psum = tree[v].sum;
        return;
    }
    int tm = (tl+tr)>>1;
    if(pos<=tm) upd(pos, val, v<<1, tl, tm);
    else upd(pos, val, v<<1|1, tm+1, tr);
    tree[v].sum = tree[v<<1].sum+tree[v<<1|1].sum;
    tree[v].psum = min(tree[v<<1].psum, tree[v<<1].sum+min(tree[v<<1|1].psum, 0ll));
}

node query(int l, int r, int v = 1, int tl = 0, int tr = N-1){
    if(l<=tl && tr<=r) return tree[v];
    int tm = (tl+tr)>>1;
    if(r<=tm) return query(l, r, v<<1, tl, tm);
    else if(l>tm) return query(l, r, v<<1|1, tm+1, tr);
    node a = query(l, r, v<<1, tl, tm), b = query(l, r, v<<1|1, tm+1, tr);
    return {a.sum+b.sum, min(a.psum, a.sum+min(0ll, b.psum))};
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for(int i = 0; i<3; ++i)
        for(int j = 0; j<n; ++j){
            int a; cin >> a; --a;
            pos[i][a] = j;
        }
    for(int i = 0; i<n; ++i)
        upd(pos[0][i], pos[1][i]+pos[2][i]-2*pos[0][i]);
    while(q--){
        int _; cin >> _;
        if(_==1){
            int x; cin >> x; --x;
            if(pos[0][x]==0) cout << "DA" << '\n';
            else cout << (query(0, pos[0][x]-1).psum==0?"NE":"DA") << '\n';
        } else{
            int p, a, b; cin >> p >> a >> b; --p; --a; --b;
            swap(pos[p][a], pos[p][b]);
            upd(pos[0][a], pos[1][a]+pos[2][a]-2*pos[0][a]); 
            upd(pos[0][b], pos[1][b]+pos[2][b]-2*pos[0][b]);
        }
    }
}

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