Submission #622287

#	Time	Username	Problem	Language	Result	Execution time	Memory
622287		Jomnoi	Seats (IOI18_seats)	C++17	17 / 100	4054 ms	63720 KiB

seats

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

const int MAX_N = 1e6 + 5;

int H, W;
vector <int> R, C;
int tree[4 * MAX_N];

struct State {
    int minR, maxR, minC, maxC;
}state[MAX_N];

void update(int idx, int l, int r, int q, int v) {
    if(l == r) {
        tree[idx] = v;
        return;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        update(idx * 2, l, mid, q, v);
    }
    else {
        update(idx * 2 + 1, mid + 1, r, q, v);
    }
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

void give_initial_chart(int h, int w, vector <int> r, vector <int> c) {
    H = h, W = w, R = r, C = c;
    
    int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0;
    for(int i = 0; i < H * W; i++) {
        minR = min(minR, R[i]);
        maxR = max(maxR, R[i]);
        minC = min(minC, C[i]);
        maxC = max(maxC, C[i]);
        state[i] = {minR, maxR, minC, maxC};

        update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1);
    }
}

int swap_seats(int a, int b) {
    if(a > b) {
        swap(a, b);
    }

    swap(R[a], R[b]), swap(C[a], C[b]);
    int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0;
    if(a > 0) {
        minR = state[a - 1].minR;
        maxR = state[a - 1].maxR;
        minC = state[a - 1].minC;
        maxC = state[a - 1].maxC;
    }
    for(int i = a; i <= b; i++) {
        minR = min(minR, R[i]);
        maxR = max(maxR, R[i]);
        minC = min(minC, C[i]);
        maxC = max(maxC, C[i]);
        state[i] = {minR, maxR, minC, maxC};

        update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1);
    }   
    return tree[1];
}

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