Submission #621088

#	Time	Username	Problem	Language	Result	Execution time	Memory
621088		erekle	Seats (IOI18_seats)	C++17	5 / 100	272 ms	60180 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
int h, w, n;
vector<int> r, c;
vector<vector<int>> grid;

/* Segment tree stores total number of the following for each index
00 A
01 (one one, rest zeros)

11 B
10 (one zero, rest ones)

01 C
10 (diagonals)

Where 0s represent values in the grid <= that index,
and 1s represent values > that index

 An index is the largest index in a good rectangle
if and only if the total number of these is 4.
 The sum can never be less than four since there have to be
at least one of each type of corner (type A).
 We add padding of 0s surrounding the grid.
*/

struct Node {
    int minSum = 0, minCnt = 1;
    int prop = 0;
    Node * left, * right;
    Node() {}
    Node(int sz): minCnt(sz) {}
};
void propagate(Node * base) {
    base->left->prop += base->prop;
    base->right->prop += base->prop;
    base->left->minSum += base->prop;
    base->right->minSum += base->prop;
    base->prop = 0;
}
// [l, r), [ql, qr)
void update(Node * &base, int l, int r, int ql, int qr, int delta) {
    if (r <= ql || qr <= l) return;
    if (ql <= l && r <= qr) {
        base->minSum += delta;
        base->prop += delta;
        return;
    }

    int mid = (l+r)/2;
    if (!base->left) base->left = new Node(mid-l);
    if (!base->right) base->right = new Node(r-mid);
    propagate(base);

    update(base->left, l, mid, ql, qr, delta);
    update(base->right, mid, r, ql, qr, delta);

    // Recalculate values for base
    if (base->left->minSum == base->right->minSum) {
        base->minSum = base->left->minSum;
        base->minCnt = base->left->minCnt + base->right->minCnt;
    } else if (base->left->minSum < base->right->minSum) {
        base->minSum = base->left->minSum;
        base->minCnt = base->left->minCnt;
    } else {
        base->minSum = base->right->minSum;
        base->minCnt = base->right->minCnt;
    }
}

Node * root;

int getGrid(int x, int y) {
    if (x < 0 || y < 0 || x >= h || y >= w) return n; // always 0
    return grid[x][y];
}

// Update segment tree using 2x2 rectangle with top left at x, y
void updateRectangle(int x, int y, bool remove, int avoid = -1) {
    int id[4];
    id[0] = getGrid(x, y);
    id[1] = getGrid(x+1, y);
    id[2] = getGrid(x, y+1);
    id[3] = getGrid(x+1, y+1);
    sort(id, id+4);
    
    for (int i : id) {
        if (i == avoid) return;
    }

    int value = (remove ? -1 : +1);
    if (id[0] != n && id[1] != n && (r[id[0]] == r[id[1]] || c[id[0]] == c[id[1]])) {
        if (id[0] != id[1]) update(root, 0, n, id[0], id[1], value);
        if (id[2] != id[3]) update(root, 0, n, id[2], id[3], value);
    } else {
        if (id[0] != id[3]) update(root, 0, n, id[0], id[3], value);
    }
    // checking that ids are not equal since they may both be n
    // (both positions either outside the grid in the padding of 0s)
}
void updateAround(int i, bool remove = false, int avoid = -1) {
    int x = r[i], y = c[i];
    updateRectangle(x, y, remove, avoid);
    updateRectangle(x, y-1, remove, avoid);
    updateRectangle(x-1, y, remove, avoid);
    updateRectangle(x-1, y-1, remove, avoid);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H, w = W, r = R, c = C;
    n = h*w;
    root = new Node(n);
    grid = vector<vector<int>>(h, vector<int>(w));
    for (int i = 0; i < n; ++i) grid[r[i]][c[i]] = i;
    for (int x = -1; x < h; ++x) {
        for (int y = -1; y < w; ++y) updateRectangle(x, y, false);
    }
}

int getFours() {
    if (root->minSum == 4) return root->minCnt;
    else assert(false); // this should never happen (index 0 and index n-1 will always have value 4)
}

int swap_seats(int a, int b) {
    // Remove from segment tree
    updateAround(a, true);
    updateAround(b, true, a); // avoid a (avoid removing rectangles with both a and b twice)
    // Swap positions
    swap(grid[r[a]][c[a]], grid[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    // Add back to segment tree
    updateAround(a, false);
    updateAround(b, false, a);
    return getFours();
}

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