Submission #76216

#	Time	Username	Problem	Language	Result	Execution time	Memory
76216		imeimi2000	Seats (IOI18_seats)	C++17	100 / 100	2001 ms	107648 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 {
        int mn, ct, lz;
        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 init(int i, int s, int e, const vector<int> &v) {
        if (s == e) {
            seg[i].mn = v[s];
            seg[i].ct = 1;
            seg[i].lz = 0;
            return;
        }
        int m = (s + e) / 2;
        init(i << 1, s, m, v);
        init(i << 1 | 1, m + 1, e, v);
        seg[i] = seg[i << 1] + seg[i << 1 | 1];
    }
    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, int 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);
}
 
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;
    }
    vector<int> sum(n + 1, 0);
    for (int i = 0; i <= h; ++i) {
        for (int j = 0; j <= w; ++j) {
            int A[4] = { getIdx(i - 1, j - 1), getIdx(i - 1, j)
                , getIdx(i, j - 1), getIdx(i, j) };
            sort(A, A + 4);
            sum[A[0]] += 1;
            sum[A[1]] -= 1;
            sum[A[2]] += 1;
            sum[A[3]] -= 1;
        }
    }
    for (int i = 1; i < n; ++i) sum[i] += sum[i - 1];
    seg.init(1, 0, n - 1, sum);
}
 
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: 30 / 30