Submission #599724

#	Time	Username	Problem	Language	Result	Execution time	Memory
599724		skittles1412	Seats (IOI18_seats)	C++17	17 / 100	4094 ms	134804 KiB

seats

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

template <typename T, typename Op = plus<T>>
struct ST {
    int n;
    Op op;
    vector<T> arr, v;

    ST() : ST(vector<T> {}) {}
    ST(const vector<T>& arr) : n(sz(arr)), op(), arr(arr), v(4 * n) {
        if (n) {
            build(1, 0, n - 1);
        }
    }

    void build(int o, int l, int r) {
        if (l == r) {
            v[o] = arr[l];
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = op(v[lc], v[rc]);
    }

    void update(int o, int l, int r, int ind, const T& x) {
        if (l == r) {
            v[o] = x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ind <= mid) {
            update(lc, l, mid, ind, x);

        } else {
            update(rc, mid + 1, r, ind, x);
        }
    }

    void update(int ind, const T& x) {
        update(1, 0, n - 1, ind, x);
    }

    T query(int o, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return v[o];
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            if (mid < qr) {
                return op(query(lc, l, mid, ql, qr),
                          query(rc, mid + 1, r, ql, qr));
            }
            return query(lc, l, mid, ql, qr);
        }
        return query(rc, mid + 1, r, ql, qr);
    }
};

struct Mn {
    int operator()(int a, int b) const {
        return min(a, b);
    }
};

struct Mx {
    int operator()(int a, int b) const {
        return max(a, b);
    }
};

struct Node {
    int rmn, rmx, cmn, cmx;

    Node& operator+=(const Node& n) {
        rmn = min(rmn, n.rmn);
        rmx = max(rmx, n.rmx);
        cmn = min(cmn, n.cmn);
        cmx = max(cmx, n.cmx);
        return *this;
    }

    bool check(int i) const {
        return (rmx - rmn + 1) * (cmx - cmn + 1) == i + 1;
    }

    friend Node operator+(Node a, const Node& b) {
        return a += b;
    }

    static Node from(int r, int c) {
        return {r, r, c, c};
    }
};

int n, m, ans;
vector<int> r, c;
vector<Node> nodes;
ST<int, Mn> rmn, cmn;
ST<int, Mx> rmx, cmx;

void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
    n = _n;
    m = _m;
    r = _r;
    c = _c;
    rmn = r;
    rmx = r;
    cmn = c;
    cmx = c;
    for (int i = 0; i < n * m; i++) {
        Node cur = Node::from(r[i], c[i]);
        if (!i) {
            nodes.push_back(cur);
        } else {
            nodes.push_back(nodes.back() + cur);
        }
        ans += nodes[i].check(i);
    }
}

int swap_seats(int a, int b) {
    if (a > b) {
        swap(a, b);
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    for (int ind : {a, b}) {
        rmn.update(ind, r[ind]);
        rmx.update(ind, r[ind]);
        cmn.update(ind, c[ind]);
        cmx.update(ind, c[ind]);
    }
    for (int i = a; i <= b; i++) {
        ans -= nodes[i].check(i);
        Node cur = Node::from(r[i], c[i]);
        if (!i) {
            nodes[i] = cur;
        } else {
            nodes[i] = nodes[i - 1] + cur;
        }
        ans += nodes[i].check(i);
    }
    return ans;
}

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