Submission #1248672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248672		countless	Seats (IOI18_seats)	C++20	5 / 100	4096 ms	212164 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 l, r;
    int mn, mx;
    segtree *left, *right;

    void merge() {
        mn = min(left->mn, right->mn);
        mx = max(left->mx, right->mx);
    }

    segtree(int l, int r, vector<int> &a) : l(l), r(r) {
        if (l == r) {
            mn = mx = a[l];
            return;
        }

        int m = (l+r) / 2;
        left = new segtree(l, m, a);
        right = new segtree(m+1, r, a);
        merge();
    }

    void update(int ind, int upd) {
        if (l == r) {
            mn = mx = upd;
            return;
        }

        int m = (l+r) / 2;
        if (ind <= m) left->update(ind, upd);
        else right->update(ind, upd);
        merge();
    }

    pair<int, int> query(int ql, int qr) {
        if (ql > r or qr < l) return {INF, -INF};
        if (ql <= l and r <= qr) return {mn, mx};

        auto [mnl, mxl] = left->query(ql, qr);
        auto [mnr, mxr] = right->query(ql, qr);
        return {min(mnl, mnr), max(mxl, mxr)};
    }
};

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;
    // r = vector<ll>(R.begin(), R.end());
    // c = vector<ll>(C.begin(), C.end());

    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);
        if (que == i+1) {
            res++;
            i++;
        } else {
            i = que - 1;
        }
    }

    return res;
}

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