Submission #586906

#	Time	Username	Problem	Language	Result	Execution time	Memory
586906		eecs	Tenis (COI19_tenis)	C++17	100 / 100	155 ms	5048 KiB

tenis

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

const int maxn = 100010;
int n, m, p[3][maxn], q[3][maxn];

#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
int mn[maxn << 2], tag[maxn << 2];

void apply(int k, int v) {
    mn[k] += v, tag[k] += v;
}

void pushdown(int k) {
    if (tag[k]) apply(ls, tag[k]), apply(rs, tag[k]), tag[k] = 0;
}

void add(int k, int l, int r, int ql, int qr, int v) {
    if (l >= ql && r <= qr) return apply(k, v);
    pushdown(k);
    if (mid >= ql) add(ls, l, mid, ql, qr, v);
    if (mid < qr) add(rs, mid + 1, r, ql, qr, v);
    mn[k] = min(mn[ls], mn[rs]);
}

int query(int k, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return mn[k];
    pushdown(k);
    int s = INT_MAX;
    if (mid >= ql) s = query(ls, l, mid, ql, qr);
    if (mid < qr) s = min(s, query(rs, mid + 1, r, ql, qr));
    return s;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i : {0, 1, 2}) {
        for (int j = 1; j <= n; j++) {
            cin >> p[i][j], q[i][p[i][j]] = j;
        }
    }
    auto upd = [&](int x, int coef) {
        for (int i : {1, 2}) if (q[i][x] < q[0][x]) {
            add(1, 1, n, q[i][x], q[0][x] - 1, coef);
        }
    };
    for (int i = 1; i <= n; i++) {
        upd(i, 1);
    }
    while (m--) {
        int op, x, y, z;
        cin >> op >> x;
        if (op == 1) {
            int i = q[0][x];
            cout << (i == 1 || query(1, 1, n, 1, i - 1) ? "DA\n" : "NE\n");
        } else {
            cin >> y >> z, x--;
            upd(y, -1), upd(z, -1);
            swap(p[x][q[x][y]], p[x][q[x][z]]), swap(q[x][y], q[x][z]);
            upd(y, 1), upd(z, 1);
        }
    }
    return 0;
}

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