Submission #1067088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067088		TheQuantiX	Seats (IOI18_seats)	C++17	37 / 100	4030 ms	165304 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using ll = int;

constexpr ll INF = 1000000000LL;

ll n, m, q, k, x, y, a, b, c;
vector< pair<ll, ll> > v;
pair<ll, ll> h[1000001];
pair<ll, ll> w[1000001];
ll ans = 0;

struct segtree {
    ll n;
    array< pair<ll, ll>, 4000001 > mintr;
    array< pair<ll, ll>, 4000001 > maxtr;

    void build(ll x, ll l, ll r) {
        if (l == r) {
            mintr[x] = {v[l].first, v[l].second};
            maxtr[x] = {v[l].first, v[l].second};
            // cout << x << ' ' << mintr[x] << ' ' << maxtr[x] << '\n';
            return;
        }
        ll mid = (r + l) / 2;
        build(x * 2 + 1, l, mid);
        build(x * 2 + 2, mid + 1, r);
        mintr[x] = {min(mintr[x * 2 + 1].first, mintr[x * 2 + 2].first), min(mintr[x * 2 + 1].second, mintr[x * 2 + 2].second)};
        maxtr[x] = {max(maxtr[x * 2 + 1].first, maxtr[x * 2 + 2].first), max(maxtr[x * 2 + 1].second, maxtr[x * 2 + 2].second)};
        // cout << x << ' ' << mintr[x] << ' ' << maxtr[x] << '\n';
    }

    segtree() : n(0) {}

    segtree(ll N) : n(N) {
        build(0, 0, n - 1);
    }

    void upd(ll x, ll l, ll r, ll idx, pair<ll, ll> val) {
        if (l == r) {
            mintr[x] = {val.first, val.second};
            maxtr[x] = {val.first, val.second};
            return;
        }
        ll mid = (r + l) / 2;
        if (idx <= mid) {
            upd(x * 2 + 1, l, mid, idx, val);
        }
        else {
            upd(x * 2 + 2, mid + 1, r, idx, val);
        }
        mintr[x] = {min(mintr[x * 2 + 1].first, mintr[x * 2 + 2].first), min(mintr[x * 2 + 1].second, mintr[x * 2 + 2].second)};
        maxtr[x] = {max(maxtr[x * 2 + 1].first, maxtr[x * 2 + 2].first), max(maxtr[x * 2 + 1].second, maxtr[x * 2 + 2].second)};
    }

    pair<ll, ll> getmx(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return {-INF, -INF};
        }
        if (r < L) {
            return {-INF, -INF};
        }
        if (R < l) {
            return {-INF, -INF};
        }
        if (L <= l && r <= R) {
            // cout << x << ' ' << l << ' ' << r << ' ' << L << ' ' << R << '\n';
            // cout << maxtr[x] << '\n';
            return maxtr[x];
        }
        ll mid = (r + l) / 2;
        auto p1 = getmx(x * 2 + 1, l, mid, L, R), p2 = getmx(x * 2 + 2, mid + 1, r, L, R);
        return {max(p1.first, p2.first), max(p1.second, p2.second)};
    }

    pair<ll, ll> getmn(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return {INF, INF};
        }
        if (r < L) {
            return {INF, INF};
        }
        if (R < l) {
            return {INF, INF};
        }
        if (L <= l && r <= R) {
            return mintr[x];
        }
        ll mid = (r + l) / 2;
        auto p1 = getmn(x * 2 + 1, l, mid, L, R), p2 = getmn(x * 2 + 2, mid + 1, r, L, R);
        return {min(p1.first, p2.first), min(p1.second, p2.second)};
    }
};

segtree sg;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H;
    m = W;
    for (int i = 0; i < n * m; i++) {
        v.push_back({R[i], C[i]});
    }
    if (n <= 1000 && m <= 1000) {
        sg = segtree(n * m);
    }
    else {
        for (int i = 0; i <= n * m; i++) {
            h[i] = {INF, -INF};
            w[i] = {INF, -INF};
        }
        for (int i = 1; i <= n * m; i++) {
            h[i].first = min(h[i - 1].first, v[i - 1].first);
            h[i].second = max(h[i - 1].second, v[i - 1].first);
            w[i].first = min(w[i - 1].first, v[i - 1].second);
            w[i].second = max(w[i - 1].second, v[i - 1].second);
        }
        for (int i = 1; i <= n * m; i++) {
            if ((h[i].second - h[i].first + 1) * (w[i].second - w[i].first + 1) == i) {
                ans++;
            }
        }
    }
}

int swap_seats(int a, int b) {
    if (n <= 1000 && m <= 1000) {
        swap(v[a], v[b]);
        sg.upd(0, 0, n * m - 1, a, v[a]);
        sg.upd(0, 0, n * m - 1, b, v[b]);
        // cout << "DEBUG" << endl;
        // pair<ll, ll> mn1 = sg.getmn(0, 0, n * m - 1, 0, 1);
        // pair<ll, ll> mx1 = sg.getmx(0, 0, n * m - 1, 0, 1);
        // cout << mn1.first << ' ' << mx1.first << '\n';
        // cout << mn1.second << ' ' << mx1.second << endl;
        int ans = 1;
        pair<ll, ll> mn = {v[0].first, v[0].second};
        pair<ll, ll> mx = {v[0].first, v[0].second};
        while ((mx.first - mn.first + 1) * (mx.second - mn.second + 1) != n * m) {
            ll idx = (mx.first - mn.first + 1) * (mx.second - mn.second + 1);
            // cout << idx << endl;
            mn = sg.getmn(0, 0, n * m - 1, 0, idx);
            mx = sg.getmx(0, 0, n * m - 1, 0, idx);
            while ((mx.first - mn.first + 1) * (mx.second - mn.second + 1) != idx + 1) {
                idx = (mx.first - mn.first + 1) * (mx.second - mn.second + 1) - 1;
                mn = sg.getmn(0, 0, n * m - 1, 0, idx);
                mx = sg.getmx(0, 0, n * m - 1, 0, idx);
            }
            ans++;
        }
        return ans;
    }
    else {
        if (a > b) {
            swap(a, b);
        }
        for (int i = a + 1; i <= b + 1; i++) {
            // cout << i << ' ' << (h[i].second - h[i].first + 1) << ' ' << (w[i].second - w[i].first + 1) << '\n';
            if ((h[i].second - h[i].first + 1) * (w[i].second - w[i].first + 1) == i) {
                ans--;
            }
        }
        swap(v[a], v[b]);
        for (int i = a + 1; i <= b + 1; i++) {
            h[i].first = min(h[i - 1].first, v[i - 1].first);
            h[i].second = max(h[i - 1].second, v[i - 1].first);
            w[i].first = min(w[i - 1].first, v[i - 1].second);
            w[i].second = max(w[i - 1].second, v[i - 1].second);
            // cout << i << ' ' << (h[i].second - h[i].first + 1) << ' ' << (w[i].second - w[i].first + 1) << '\n';
            if ((h[i].second - h[i].first + 1) * (w[i].second - w[i].first + 1) == i) {
                ans++;
            }
        }
        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