Submission #782574

#	Time	Username	Problem	Language	Result	Execution time	Memory
782574		resting	Seats (IOI18_seats)	C++17	100 / 100	3986 ms	251260 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define set owo

//segment tree base
struct segtree {
    int l, r;
    segtree* lc, * rc;
    segtree* getmem();
    int mn = 0, mncnt;
    int lz = 0;
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r), mncnt(r - l + 1) {
        if (l == r) return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void apply(int x) {
        lz += x; mn += x;
    }
    void push() {
        if (l == r) return;
        lc->apply(lz); rc->apply(lz);
        lz = 0;
    }
    void pull() {
        mn = min(lc->mn, rc->mn); mncnt = 0;
        if (lc->mn == mn) mncnt += lc->mncnt;
        if (rc->mn == mn) mncnt += rc->mncnt;
    }
    void upd(int ql, int qr, int qv) {
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(qv);
            return;
        }
        push();
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        pull();
    }

    //debugging only
    int q(int v, int ad = 0) {
        ad += lz;
        if (l == r) return ad;
        if (v <= lc->r) return lc->q(v, ad);
        return rc->q(v, ad);
    }
}uwu, mem[4000005];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
vector<int> r, c;
int h, w, n, dx[] = { -1, 0, 1, 0, -1, 0 }, dy[] = { 0, -1, 0, 1, 0, 0 };
vector<vector<int>> g;

bool inbound(int r, int c) {
    return r >= 0 && c >= 0 && r < h && c < w;
}

void upd(int r, int c, int t) {
    for (int i = 0; i < 4; i++) {
        int a = inbound(r + dx[i], c + dy[i]) ? g[r + dx[i]][c + dy[i]] : n;
        int b = inbound(r + dx[i + 1], c + dy[i + 1]) ? g[r + dx[i + 1]][c + dy[i + 1]] : n;
        if (a > g[r][c] && b > g[r][c]) {
            uwu.upd(g[r][c], n - 1, t);
            uwu.upd(min(a, b), n - 1, -t);
        }
        if (a < g[r][c] && b < g[r][c]) {
            uwu.upd(max(a, b), n - 1, t);
            uwu.upd(g[r][c], n - 1, -t);
        }
    }
}

void set(int r, int c, int v) {
    for (int i = 1; i < 6; i++) {
        if (!inbound(r + dx[i], c + dy[i])) continue;
        upd(r + dx[i], c + dy[i], -1);
    }
    g[r][c] = v;
    for (int i = 1; i < 6; i++) {
        if (!inbound(r + dx[i], c + dy[i])) continue;
        upd(r + dx[i], c + dy[i], 1);
    }
}


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H * W; h = H; w = W; r = R; c = C;
    uwu = segtree(0, n - 1);
    g = vector<vector<int>>(H, vector<int>(W, 0));
    for (int i = 0; i < n; i++) {
        g[r[i]][c[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        upd(r[i], c[i], 1);
    }
}

int swap_seats(int a, int b) {
    set(r[a], c[a], b);
    set(r[b], c[b], a);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    return uwu.mncnt;
}

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