Submission #599745

#	Time	Username	Problem	Language	Result	Execution time	Memory
599745		skittles1412	Seats (IOI18_seats)	C++17	37 / 100	4027 ms	149552 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())

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

    int area() const {
        return (rmx - rmn + 1) * (cmx - cmn + 1);
    }

    bool check(int i) const {
        return area() == i + 1;
    }

    bool operator==(const Node& n) const {
        return rmn == n.rmn && rmx == n.rmx && cmn == n.cmn && cmx == n.cmx;
    }

    bool operator!=(const Node& n) const {
        return !(*this == n);
    }

    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;
    }

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

    friend ostream& operator<<(ostream& out, const Node& n) {
        return out << "{" << n.rmn << ", " << n.rmx << ", " << n.cmn << ", "
                   << n.cmx << "}";
    }

    static Node def() {
        return {int(1e9), -1, int(1e9), -1};
    }

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

struct ST {
    int n;
    vector<Node> arr, v;

    ST() : ST(vector<Node> {}) {}
    ST(const vector<Node>& arr) : n(sz(arr)), 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] = v[lc] + v[rc];
    }

    void update(int o, int l, int r, int ind, const Node& 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);
        }
        v[o] = v[lc] + v[rc];
    }

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

    Node 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 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);
    }

    Node query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    void solve(int o, int l, int r, const Node& pref, vector<int>& out) {
        if (pref == pref + v[o]) {
            return;
        } else if (l == r) {
            out.push_back((pref + v[o]).area());
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        solve(lc, l, mid, pref, out);
        solve(rc, mid + 1, r, pref + v[lc], out);
    }

    int solve() {
        vector<int> arr;
        solve(1, 0, n - 1, Node::def(), arr);
        int ans = 0;
        for (auto& a : arr) {
            ans += query(0, a - 1).check(a - 1);
        }
        return ans;
    }
};

int n, m, ans;
vector<int> r, c;
vector<Node> nodes;
ST st;

void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
    n = _n;
    m = _m;
    r = _r;
    c = _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);
    }
    vector<Node> arr;
    for (int i = 0; i < n * m; i++) {
        arr.push_back(Node::from(r[i], c[i]));
    }
    st = arr;
}

int swap_seats(int a, int b) {
    if (a > b) {
        swap(a, b);
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    st.update(a, Node::from(r[a], c[a]));
    st.update(b, Node::from(r[b], c[b]));
    if (n <= 1000 && m <= 1000) {
        return st.solve();
    }
    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: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30