Submission #763115

#	Time	Username	Problem	Language	Result	Execution time	Memory
763115		t6twotwo	Seats (IOI18_seats)	C++17	17 / 100	4030 ms	56396 KiB

seats

#include "seats.h"
using namespace std;
int N, M, ans;
vector<int> A, B, xmax, xmin, ymax, ymin;
int f(int k) {
    return (xmax[k] - xmin[k] + 1) * (ymax[k] - ymin[k] + 1) == k;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    N = H, M = W;
    A = R, B = C;
    xmax.resize(N * M + 1, -1);
    xmin.resize(N * M + 1, N);
    ymax.resize(N * M + 1, -1);
    ymin.resize(N * M + 1, M);
    for (int i = 0; i < N * M; i++) {
        xmax[i + 1] = max(xmax[i], A[i]);
        xmin[i + 1] = min(xmin[i], A[i]);
        ymax[i + 1] = max(ymax[i], B[i]);
        ymin[i + 1] = min(ymin[i], B[i]);
        ans += f(i + 1);
    }
}
int swap_seats(int a, int b) {
    swap(A[a], A[b]);
    swap(B[a], B[b]);
    for (int i = min(a, b); i <= max(a, b); i++) {
        ans -= f(i + 1);
        xmax[i + 1] = max(xmax[i], A[i]);
        xmin[i + 1] = min(xmin[i], A[i]);
        ymax[i + 1] = max(ymax[i], B[i]);
        ymin[i + 1] = min(ymin[i], B[i]);
        ans += f(i + 1);
    }
    return ans;
}

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