Submission #1248687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248687		countless	Seats (IOI18_seats)	C++20	0 / 100	4094 ms	65332 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
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;
    }
};

struct sumtree {
    int n, t;
    vector<int> tree;
    sumtree(int l, int r) {
        n = r+1;
        t = 1;
        while (t < n) t <<= 1;
        tree.assign(2*t, 0);

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

        for (int i = t-1; i >= 0; i--) {
            tree[i] = tree[i<<1] + tree[i<<1|1];
        }
    }

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

    int query(int l, int r) {
        l += t, r += t;
        int res = 0;
        while (l <= r) {
            if (l & 1) {
                res += tree[l];
                l++;
            }

            if (!(r & 1)) {
                res += tree[r];
                r--;
            }

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

        return res;
    }
};

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

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

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

    ts = new sumtree(0, h+w-1);

    int r1, c1, r2, c2;
    r1 = r2 = r[0];
    c1 = c2 = c[0];
    ts->update(0, check(r1, c1, r2, c2, 0));

    for (int i = 1; i < h * w; i++) {
        r1 = min(r1, r[i]);
        r2 = max(r2, r[i]);

        c1 = min(c1, c[i]);
        c2 = max(c2, c[i]);

        ts->update(i, check(r1, c1, r2, c2, i));
    }
}

// to opt: process in linear order (must always eq 0, etc)
int swap_seats(int a, int b) {
    // perform swap
    if (a > b) swap(a, b);
    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
    // sanity check, unsure if my segtree with return default if -1
    auto [r1, r2] = (a ? str->query(0, a-1) : make_pair(INF, -INF));
    auto [c1, c2] = (a ? stc->query(0, a-1) : make_pair(INF, -INF));
    for (int i = a; i <= b; i++) {
        r1 = min(r1, r[i]);
        r2 = max(r2, r[i]);

        c1 = min(c1, c[i]);
        c2 = max(c2, c[i]);

        ts->update(i, check(r1, c1, r2, c2, i));
    }

    // for (int i = 0; i < ts->tree.size(); i++) cerr << ts->tree[i] << " ";
    // cerr << endl;
    return ts->tree[1];
}

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