Submission #647036

#	Time	Username	Problem	Language	Result	Execution time	Memory
647036		Joshc	Seats (IOI18_seats)	C++17	100 / 100	3071 ms	141748 KiB

seats

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

#define ll long long

vector<vector<int>> g;
vector<int> r, c;
int h, w;


struct node {
    int min = 0, cnt = 1, lazy = 0;
};

vector<node> seg(4000100);

void push(int v) {
    seg[v<<1].min += seg[v].lazy;
    seg[v<<1|1].min += seg[v].lazy;
    seg[v<<1].lazy += seg[v].lazy;
    seg[v<<1|1].lazy += seg[v].lazy;
    seg[v].lazy = 0;
}

void update(int v, int tl, int tr, int l, int r, ll delta) {
    if (l > r) return;
    if (l == tl && r == tr) {
        seg[v].min += delta;
        seg[v].lazy += delta;
    } else {
        int tm = (tl+tr) >> 1;
        push(v);
        update(v<<1, tl, tm, l, min(r, tm), delta);
        update(v<<1|1, tm+1, tr, max(l, tm+1), r, delta);
        if (seg[v<<1].min == seg[v<<1|1].min) {
            seg[v].min = seg[v<<1].min;
            seg[v].cnt = seg[v<<1].cnt + seg[v<<1|1].cnt;
        } else if (seg[v<<1].min < seg[v<<1|1].min) {
            seg[v].min = seg[v<<1].min;
            seg[v].cnt = seg[v<<1].cnt;
        } else {
            seg[v].min = seg[v<<1|1].min;
            seg[v].cnt = seg[v<<1|1].cnt;
        }
    }
}

void process(int x, int y, int t) {
    // Process the 2*2 square with top-left corner (x, y)
    vector<int> cells;
    for (int i=x; i<x+2; i++) {
        for (int j=y; j<y+2; j++) {
            if (0 <= i && i < h && 0 <= j && j < w) cells.push_back(g[i][j]);
        }
    }
    sort(cells.begin(), cells.end());
    if (cells.size() == 1) update(1, 0, h*w-1, cells[0], h*w-1, t);
    else update(1, 0, h*w-1, cells[0], cells[1]-1, t);
    if (cells.size() == 4) update(1, 0, h*w-1, cells[2], cells[3]-1, 5*t);
}

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

int swap_seats(int a, int b) {
    vector<pair<int, int>> cells;
    for (int i=r[a]-1; i<=r[a]; i++) {
        for (int j=c[a]-1; j<=c[a]; j++) cells.emplace_back(i, j);
    }
    for (int i=r[b]-1; i<=r[b]; i++) {
        for (int j=c[b]-1; j<=c[b]; j++) cells.emplace_back(i, j);
    }
    sort(cells.begin(), cells.end());
    cells.resize(unique(cells.begin(), cells.end())-cells.begin());

    for (auto p : cells) process(p.first, p.second, -1);

    swap(r[a], r[b]);
    swap(c[a], c[b]);
    swap(g[r[a]][c[a]], g[r[b]][c[b]]);
    

    for (auto p : cells) process(p.first, p.second, 1);

    return seg[1].cnt;
}

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