Submission #1062795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062795		TAhmed33	Seats (IOI18_seats)	C++17	5 / 100	4066 ms	130032 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
const int MAXN = 1e6 + 25;
#define mid ((l  + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
int pos[MAXN], a[MAXN], n, h, w;
int v[MAXN];
bool flag = 0;
int ev (int i) {
    int sum = 0;
    sum += (a[pos[i] - 1] < i ? -1 : 1);
    sum += (a[pos[i] + 1] < i ? -1 : 1);
    return sum;
}
using info = array <int, 3>;
info make (int x) {
    return {x, 1, x};
}
info merge (info a, info b) {
    b[0] += a[2];
    if (a[0] < b[0]) {
        return {a[0], a[1], a[2] + b[2]};
    } else if (a[0] > b[0]) {
        return {b[0], b[1], a[2] + b[2]};
    } else {
        return {a[0], a[1] + b[1], a[2] + b[2]};
    }
}
struct SegmentTree {
    vector <info> tree;
    void init (int n) {
        tree.resize(4 * n);
    }
    void build (int l, int r, int node) {
        if (l == r) {
            tree[node] = make(v[l]);
        } else {
            build(l, mid, tl); build(mid + 1, r, tr);
            tree[node] = merge(tree[tl], tree[tr]);
        }
    }
    void update (int l, int r, int a, int node) {
        if (l > a || r < a) return;
        if (l == r) {
             tree[node] = make(v[a]);
            return;
        }
        update(l, mid, a, tl); update(mid + 1, r, a, tr);
        tree[node] = merge(tree[tl], tree[tr]);
    }
    info get (int l, int r, int a, int node) {
        if (l == r) {
            return tree[node];
        }
        if (a <= mid) return get(l, mid, a, tl);
        else return get(mid + 1, r, a, tr);
    }
} cur;
struct SegmentTree2 {
    int a[MAXN << 1];
    pair <int, int> tree[MAXN << 1];
    pair <int, int> merge (pair <int, int> x, pair <int, int> y) {
        return {min(x.first, y.first), max(x.second, y.second)};
    }
    void init (int l, int r, int node) {
        if (l == r) {
            tree[node] = {a[l], a[l]};
        } else {
            init(l, mid, tl); init(mid + 1, r, tr);
            tree[node] = merge(tree[tl], tree[tr]);
        }
    }
    void update (int l, int r, int a, int b, int node) {
        if (l > a || r < a) return;
        if (l == r) {
            tree[node] = {b, b};
            return;
        }
        update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
        tree[node] = merge(tree[tl], tree[tr]);
    }
    pair <int, int> get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return {1e9, 0};
        if (l >= a && r <= b) return tree[node];
        return merge(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
    }
} c1, c2;
vector <int> rr, cc;
void give_initial_chart (int H, int W, vector <int> R, vector <int> C) {
    rr = R; cc = C;
    h = H; w = W;
    flag = 0;
    if (0 && h == 1) {
        flag = 1;
        n = w;
        for (int i = 1; i <= n; i++) {
            a[C[i - 1] + 1] = i;
            pos[i] = C[i - 1] + 1;
        }
        a[0] = a[n + 1] = n + 1;
        for (int i = 1; i <= n; i++) {
            v[i] = ev(i);
        }
        cur.init(n); cur.build(1, n, 1);
        return;
    }
    for (int i = 0; i < h * w; i++) {
        c1.a[i] = R[i]; c2.a[i] = C[i];
    }
    c1.init(0, h * w - 1, 1); c2.init(0, h * w - 1, 1);
}
int swap_seats (int A, int B) {
    if (flag) {
        A++; B++;
        v[A] = 0, cur.update(1, n, A, 1);
        if (pos[A] != 1) v[a[pos[A] - 1]] = 0, cur.update(1, n, a[pos[A] - 1], 1);
        if (pos[A] != n) v[a[pos[A] + 1]] = 0, cur.update(1, n, a[pos[A] + 1], 1);
        v[B] = 0, cur.update(1, n, B, 1);
        if (pos[B] != 1) v[a[pos[B] - 1]] = 0, cur.update(1, n, a[pos[B] - 1], 1);
        if (pos[B] != n) v[a[pos[B] + 1]] = 0, cur.update(1, n, a[pos[B] + 1], 1);
        swap(a[pos[A]], a[pos[B]]);
        swap(pos[A], pos[B]);
        v[A] = ev(A), cur.update(1, n, A, 1);
        if (pos[A] != 1) v[a[pos[A] - 1]] = ev(a[pos[A] - 1]), cur.update(1, n, a[pos[A] - 1], 1);
        if (pos[A] != n) v[a[pos[A] + 1]] = ev(a[pos[A] + 1]), cur.update(1, n, a[pos[A] + 1], 1);
        v[B] = ev(B), cur.update(1, n, B, 1);
        if (pos[B] != 1) v[a[pos[B] - 1]] = ev(a[pos[B] - 1]), cur.update(1, n, a[pos[B] - 1], 1);
        if (pos[B] != n) v[a[pos[B] + 1]] = ev(a[pos[B] + 1]), cur.update(1, n, a[pos[B] + 1], 1);
        return cur.tree[1][1]; 
    }
    swap(rr[A], rr[B]);
    swap(cc[A], cc[B]);
    c1.update(0, h * w - 1, A, rr[A], 1);
    c2.update(0, h * w - 1, A, cc[A], 1);
    c1.update(0, h * w - 1, B, rr[B], 1);
    c2.update(0, h * w - 1, B, cc[B], 1);
    int pos = 0, ans = 0;
    while (pos < h * w) {
        auto [r1, r2] = c1.get(0, h * w - 1, 0, pos, 1);
        auto [c3, c4] = c2.get(0, h * w - 1, 0, pos, 1);
        int s = (r2 - r1 + 1) * (c4 - c3 + 1);
        if (pos + 1 == s) {
            ans++;
            pos++;
        } else {
            pos = s - 1;
        }
    }
    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30