Submission #1043542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043542		Zicrus	Seats (IOI18_seats)	C++17	17 / 100	4043 ms	55724 KiB

seats

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

typedef long long ll;

int n, w, h;
vector<int> x, y;
vector<int> le, ri, to, bo;
vector<bool> poss;
int res;

void give_initial_chart(int h1, int w1, vector<int> r, vector<int> c) {
    w = w1; h = h1;
    n = h*w;
    x = c; y = r;

    le = vector<int>(n);
    ri = vector<int>(n);
    to = vector<int>(n);
    bo = vector<int>(n);
    poss = vector<bool>(n);

    res = 1;
    poss[0] = true;
    int left = x[0], right = x[0], top = y[0], bot = y[0];
    le[0] = left; ri[0] = right; to[0] = top; bo[0] = bot;
    for (int i = 1; i < n; i++) {
        le[i] = left = min(left, x[i]);
        ri[i] = right = max(right, x[i]);
        to[i] = top = min(top, y[i]);
        bo[i] = bot = max(bot, y[i]);
        if ((right-left+1) * (bot-top+1) == i+1) {
            res++;
            poss[i] = true;
        }
    }
}

int swap_seats(int a, int b) {
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    if (a > b) swap(a, b);
    int left = le[max(0,a-1)], right = ri[max(0,a-1)], top = to[max(0,a-1)], bot = bo[max(0,a-1)];
    if (a == 0) {
        le[0] = left = x[0]; ri[0] = right = x[0];
        to[0] = top = y[0]; bo[0] = bot = y[0];
    }
    for (int i = max(1,a); i < b; i++) {
        res -= poss[i];
        le[i] = left = min(left, x[i]);
        ri[i] = right = max(right, x[i]);
        to[i] = top = min(top, y[i]);
        bo[i] = bot = max(bot, y[i]);
        if ((right-left+1) * (bot-top+1) == i+1) {
            res++;
            poss[i] = true;
        }
        else poss[i] = false;
    }
    return res;
}

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