Submission #233477

#	Time	Username	Problem	Language	Result	Execution time	Memory
233477		VEGAnn	Tenis (COI19_tenis)	C++14	100 / 100	225 ms	9500 KiB

tenis

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, q, loc[3][N], a[3][N], psh[4 * N];
array<int, 2> st[4 * N];

void build(int v, int l, int r){
    psh[v] = 0;

    if (l == r) {
        st[v] = {-(l + 1), l};
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void push(int v){
    if (psh[v] != 0){
        st[v][0] += psh[v];

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }

        psh[v] = 0;
    }
}

void upd(int v, int tl, int tr, int l, int r, int vl){
    push(v);
    if (l > r) return;

    if (tl == l && tr == r){
        psh[v] += vl;
        push(v);
        return;
    }

    int md = (tl + tr) >> 1;

    upd(v + v, tl, md, l, min(r, md), vl);
    upd(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void update(int vl, int ad){
    int pos = min(loc[0][vl], min(loc[1][vl], loc[2][vl]));

    upd(1, 0, n - 1, pos, n - 1, ad);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    for (int tp = 0; tp < 3; tp++)
    for (int i = 0; i < n; i++){
        cin >> a[tp][i];
        a[tp][i]--;
        loc[tp][a[tp][i]] = i;
    }

    build(1, 0, n - 1);

    for (int i = 0; i < n; i++)
        update(i, +1);

    for (; q; q--){
        int tp; cin >> tp;

        if (tp == 1){
            int x; cin >> x; x--;

            cout << (st[1][1] >= loc[0][x] ? "DA\n" : "NE\n");
        } else {
            int x, y; cin >> tp >> x >> y;
            tp--; x--; y--;

            update(x, -1);
            update(y, -1);

            swap(loc[tp][x], loc[tp][y]);
            swap(a[tp][loc[tp][x]], a[tp][loc[tp][y]]);

            update(x, 1);
            update(y, 1);
        }
    }

    return 0;
}

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