Submission #1248682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248682		countless	Seats (IOI18_seats)	C++20	25 / 100	4097 ms	57144 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

const int INF = 1e9;

struct segtree {
    int n, t;
    vector<pair<int, int>> tree;
    segtree(int l, int r, vector<int> &a) {
        n = r+1;
        t = 1;
        while (t < n) t <<= 1;
        tree.assign(2*t, {INF, -INF});

        for (int i = 0; i < n; i++) {
            tree[t + i] = {a[i], a[i]};
        }

        for (int i = t-1; i >= 0; i--) {
            tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
            tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
        }
    }

    void update(int ind, int upd) {
        int i = t + ind;
        tree[i] = {upd, upd};
        for (i >>= 1; i; i >>= 1) {
            tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
            tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
        }
    }

    pair<int, int> query(int l, int r) {
        l += t, r += t;
        pair<int, int> res = {INF, -INF};
        while (l <= r) {
            if (l & 1) {
                res.first = min(res.first, tree[l].first);
                res.second = max(res.second, tree[l].second);
                l++;
            }

            if (!(r & 1)) {
                res.first = min(res.first, tree[r].first);
                res.second = max(res.second, tree[r].second);
                r--;
            }

            l >>= 1, r >>= 1;
        }

        return res;
    }
};

int h, w;
vector<int> r, c;
segtree *str, *stc;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H, w = W, r = R, c = C;
    str = new segtree(0, h*w-1, r);
    stc = new segtree(0, h*w-1, c);
}

inline int calc(int r1, int c1, int r2, int c2) {
    int he = r2 - r1 + 1, we = c2 - c1 + 1;
    int amt = he * we;
    return amt;
}

int swap_seats(int a, int b) {
    // perform swap
    swap(r[a], r[b]);
    swap(c[a], c[b]);

    str->update(a, r[a]);
    str->update(b, r[b]);

    stc->update(a, c[a]);
    stc->update(b, c[b]);

    // count
    int res = 0;
    int r1, c1, r2, c2;
    r1 = r2 = r[0];
    c1 = c2 = c[0];
    res += calc(r1, c1, r2, c2) == 1;

    int i = 1;
    while (i < h * w) {
        auto [mnr, mxr] = str->query(0, i);
        r1 = min(r1, mnr);
        r2 = max(r2, mxr);

        auto [mnc, mxc] = stc->query(0, i);
        c1 = min(c1, mnc);
        c2 = max(c2, mxc);

        int que = calc(r1, c1, r2, c2);
        // cerr << i sp r1 sp c1 sp r2 sp c2 sp que << endl;
        if (que == i+1) res++;
        // cerr << i sp res << endl;
        if (i == max(i+1, que-1)) assert(0);
        i = max(i+1, que-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