Submission #336607

#	Time	Username	Problem	Language	Result	Execution time	Memory
336607		ryno	Tenis (COCI20_tenis)	C++14	0 / 110	1 ms	620 KiB

tenis

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
constexpr int MAX = 1 << 17;
constexpr int SHIFT = 300000;

int N, Q, pos[4][100005], tree[MAX * 2 + 5], lazy[MAX * 2 + 5];

void push(int node) {
    tree[node * 2] += lazy[node];
    lazy[node * 2] += lazy[node];
    tree[node * 2 + 1] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
    lazy[node] = 0;
}

void incr(int tl, int tr, int val, int node = 1, int l = 1, int r = MAX - 1) {
    if (l > r || tl > r || l > tr || tl > tr) return;
    if (tl <= l && l <= r && r <= tr) {
        tree[node] += val;
        lazy[node] += val;
        return;
    }
    push(node);
    int m = (l + r) / 2;
    incr(tl, min(m, tr), val, node * 2, l, m);
    incr(max(m + 1, tl), tr, val, node * 2 + 1, m + 1, r);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

int query(int tr, int node = 1, int l = 1, int r = MAX - 1) { // tl = 1
    if (l > r || l > tr) return numeric_limits<int>::max();
    if (r <= tr) return tree[node];
    push(node);
    int m = (l + r) / 2;
    return min(
        query(min(m, tr), node * 2, l, m),
        query(tr, node * 2 + 1, m + 1, r)
    );
}

void update(int index, int val) {
    int minRank = min({ pos[1][index], pos[2][index], pos[3][index] });
    int maxRank = max({ pos[1][index], pos[2][index], pos[3][index] });
    incr(minRank, maxRank - 1, val);
}

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    //ifstream cin{ "in.txt" };
    cin >> N >> Q;
    for (int type = 1; type <= 3; ++type) {
        for (int i = 1; i <= N; ++i) {
            int a;
            cin >> a;
            pos[type][a] = i;
        }
    }
    for (int i = 1; i <= N; ++i) update(i, 1);

    for (int i = 0; i < Q; ++i) {
        int type, x, a, b;
        cin >> type;
        if (type == 1) {
            cin >> x;
            int r = min({ pos[1][x], pos[2][x], pos[3][x] });
            cout << (query(r - 1) ? "DA" : "NE") << "\n";
        }
        else {
            cin >> x >> a >> b;
            update(a, -1);
            update(b, -1);
            swap(pos[x][a], pos[x][b]);
            update(a, 1);
            update(b, 1);
        }
    }
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 15
• Subtask 3: 0 / 60