Submission #1247742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247742		makmed1337	Seats (IOI18_seats)	C++20	25 / 100	4098 ms	86836 KiB

seats

#include "seats.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>

using namespace std;

constexpr int inf = 1e9;
struct Tree {
    struct T {
        int mn = inf, mx = -inf;
        static T from(int x) { return {x, x}; }
        T static combine(T f, T s) { return {min(f.mn, s.mn), max(f.mx, s.mx)}; }
    };

    vector<T> tree;
    void pull(int i) { tree[i] = T::combine(tree[2 * i], tree[2 * i + 1]); }

    void init(vector<int> const &base) {
        int n = base.size();
        tree.resize(4 * n);
        _build(1, 0, n - 1, base);
    }

    void _build(int i, int l, int r, vector<int> const &base) {
        if (l == r) {
            tree[i] = T::from(base[l]);
            return;
        }

        int m = (l + r) / 2;
        _build(2 * i, l, m, base);
        _build(2 * i + 1, m + 1, r, base);
        pull(i);
    }

    T get(int i, int l, int r, int lb, int rb) const {
        if (r < lb || l > rb) {
            return {};
        }

        if (lb <= l && r <= rb) {
            return tree[i];
        }

        int m = (l + r) / 2;
        return T::combine(get(2 * i, l, m, lb, rb), get(2 * i + 1, m + 1, r, lb, rb));
    }

    void update(int i, int l, int r, int pos, int x) {
        if (pos < l || pos > r) {
            return;
        }

        if (l == r) {
            tree[i] = T::from(x);
            return;
        }

        int m = (l + r) / 2;
        update(2 * i, l, m, pos, x);
        update(2 * i + 1, m + 1, r, pos, x);
        pull(i);
    }
};

vector<int> r, c;
Tree rt, ct;
int n;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H * W;

    r = R;
    c = C;
    rt.init(r);
    ct.init(c);
}

int swap_seats(int a, int b) {
    swap(r[a], r[b]);
    rt.update(1, 0, n - 1, a, r[a]);
    rt.update(1, 0, n - 1, b, r[b]);

    swap(c[a], c[b]);
    ct.update(1, 0, n - 1, a, c[a]);
    ct.update(1, 0, n - 1, b, c[b]);

    int res = 0;
    int i = 0;
    while (i < n) {
        auto rr = rt.get(1, 0, n - 1, 0, i);
        auto cc = ct.get(1, 0, n - 1, 0, i);
        int sz = (rr.mx - rr.mn + 1) * (cc.mx - cc.mn + 1);
        if (sz == i + 1) {
            res++;
            ++i;
        } else {
            i = sz - 1;
        }
    }
    return res;
}

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