Submission #117994

#	Time	Username	Problem	Language	Result	Execution time	Memory
117994		keko37	Tenis (COI19_tenis)	C++14	100 / 100	426 ms	9536 KiB

tenis

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

int n, q, ofs = 1;
int p[4][MAXN], pos[4][MAXN], mx[MAXN], val[MAXN];

struct node {
    int val, pos, prop;
    node () {}
    node (int _val, int _pos, int _prop) {
        val = _val; pos = _pos; prop = _prop;
    }
} t[MAXN*3];

void ispis () {
    for (int i=0; i<2*ofs; i++) {
        cout << "bla " << i << "  " << t[i].val << " " << t[i].pos <<  " " << t[i].prop << endl;
    }
}

void propagate (int x) {
    if (t[x].prop == 0) return;
    t[x].val += t[x].prop;
    if (x < ofs) {
        t[2*x].prop += t[x].prop;
        t[2*x+1].prop += t[x].prop;
    }
    t[x].prop = 0;
}

node spoji (node a, node b) {
    if (a.val <= b.val) return a; else return b;
}

void update (int x, int from, int to, int low, int high, int br) {
    //cout << "update " << from << " " << to << "  " << br << endl;
    propagate(x);
    if (from <= low && high <= to) {
        t[x].prop += br;
        propagate(x);
        return;
    }
    if (to < low || high < from) return;
    update(2*x, from, to, low, (low + high)/2, br);
    update(2*x+1, from, to, (low + high)/2+1, high, br);
    t[x] = spoji(t[2*x], t[2*x+1]);
}

node upit (int x, int from, int to, int low, int high) {
    propagate(x);
    if (from <= low && high <= to) return t[x];
    if (to < low || high < from) return node(MAXN, n, 0);
    return spoji(upit(2*x, from, to, low, (low + high)/2), upit(2*x+1, from, to, (low + high)/2+1, high));
}

void ubaci (int v, int x, int sign) {
    if (x >= v) return;
    update(1, x-1, v-2, 0, ofs-1, sign);
}


void build () {
    while (ofs < n) ofs *= 2;
    for (int i=0; i<ofs; i++) {
        if (i < n) t[i + ofs] = node(0, i, 0); else t[i + ofs] = node(MAXN, n, 0);
    }
    for (int i=ofs-1; i>0; i--) {
        t[i] = spoji(t[2*i], t[2*i+1]);
    }
    //ispis();
    for (int i=1; i<=n; i++){
        ubaci(val[i], i, 1);
    }
}

void novi (int r, int s) {
    int v = 0;
    for (int i=1; i<=3; i++) {
        v = max(v, mx[p[i][s]]);
    }
    if (v != val[s]) {
        ubaci(val[s], s, -1);
        val[s] = v;
        ubaci(val[s], s, 1);
    }
}

void promjeni (int r, int a, int b) {
    //cout << "mijenjam " << r << " " << a << " " << b << endl;
    int x = pos[r][a], y = pos[r][b];
    p[r][x] = b; p[r][y] = a;
    pos[r][a] = y; pos[r][b] = x;
    mx[a] = mx[b] = 0;
    for (int i=1; i<=3; i++) {
        mx[a] = max(mx[a], pos[i][a]);
        mx[b] = max(mx[b], pos[i][b]);
    }
    for (int i=1; i<=3; i++) {
        novi(i, pos[i][a]);
        novi(i, pos[i][b]);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i=1; i<=3; i++) {
        for (int j=1; j<=n; j++) {
            cin >> p[i][j];
            pos[i][p[i][j]] = j;
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=3; j++) {
            mx[i] = max(mx[i], pos[j][i]);
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=3; j++) {
            val[i] = max(val[i], mx[p[j][i]]);
        }
    }
    build();
    //ispis();
    for (int i=0; i<q; i++) {
        int tip;
        cin >> tip;
        if (tip == 1) {
            int a;
            cin >> a;
            int lim = upit(1, 0, n-1, 0, ofs-1).pos + 1;
            if (mx[a] <= lim) cout << "DA\n"; else cout << "NE\n";
        } else {
            int r, a, b;
            cin >> r >> a >> b;
            promjeni(r, a, b);
        }
    }
    return 0;
}

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