Submission #75156

#	Time	Username	Problem	Language	Result	Execution time	Memory
75156		imeimi2000	Seats (IOI18_seats)	C++17	70 / 100	4029 ms	128256 KiB

seats

#include "seats.h"
#include <algorithm>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int h, w, n;

vector<int> R, C;
vector<vector<int>> idx;

struct segtree {
    struct node {
        llong mn, ct, lz;
        node() : mn(0), ct(1), lz(0) {}
        node operator+(const node &p) const {
            node ret;
            ret.mn = min(mn, p.mn);
            ret.ct = 0;
            if (ret.mn == mn) ret.ct += ct;
            if (ret.mn == p.mn) ret.ct += p.ct;
            ret.lz = 0;
            return ret;
        }
    } seg[1 << 21];
    
    void spread(int i) {
        seg[i << 1].mn += seg[i].lz;
        seg[i << 1].lz += seg[i].lz;
        seg[i << 1 | 1].mn += seg[i].lz;
        seg[i << 1 | 1].lz += seg[i].lz;
        seg[i].lz = 0;
    }
    void update(int i, int s, int e, int x, int y, llong v) {
        if (e < x || y < s) return;
        if (x <= s && e <= y) {
            seg[i].mn += v;
            seg[i].lz += v;
            return;
        }
        spread(i);
        int m = (s + e) / 2;
        update(i << 1, s, m, x, y, v);
        update(i << 1 | 1, m + 1, e, x, y, v);
        seg[i] = seg[i << 1] + seg[i << 1 | 1];
    }
    int get() const {
        return seg[1].ct;
    }
} seg;

int getIdx(int x, int y) {
    if (x < 0 || h <= x || y < 0 || w <= y) return n;
    return idx[x][y];
}

void update(int x, int y, int v) {
    int A[4] = { getIdx(x - 1, y - 1), getIdx(x - 1, y)
                , getIdx(x, y - 1), getIdx(x, y) };
    sort(A, A + 4);
    seg.update(1, 0, n - 1, A[0], A[1] - 1, v);
    seg.update(1, 0, n - 1, A[2], A[3] - 1, v * (1ll << 30));
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    idx.resize(H, vector<int>(W, 0));
    ::R = R; ::C = C;
    h = H; w = W; n = H * W;
    for (int i = 0; i < n; ++i) {
        idx[R[i]][C[i]] = i;
    }
    for (int i = 0; i <= h; ++i) {
        for (int j = 0; j <= w; ++j) {
            update(i, j, 1);
        }
    }
}

int swap_seats(int a, int b) {
    vector<pii> ps;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            ps.emplace_back(R[a] + i, C[a] + j);
            ps.emplace_back(R[b] + i, C[b] + j);
        }
    }
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    for (pii i : ps) update(i.first, i.second, -1);
    swap(idx[R[a]][C[a]], idx[R[b]][C[b]]);
    swap(R[a], R[b]); swap(C[a], C[b]);
    for (pii i : ps) update(i.first, i.second, 1);
    return seg.get();
}

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