Submission #1038195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038195		RecursiveCo	Seats (IOI18_seats)	C++17	17 / 100	4018 ms	56508 KiB

seats

#include <bits/stdc++.h>

using namespace std;

#define in(i) cin >> i
#define out(o) cout << o

vector<int> prefmaxc;
vector<int> prefminc;
vector<int> prefmaxr;
vector<int> prefminr;
vector<int> R;
vector<int> C;
int ans = 0;

void give_initial_chart(int H, int W, vector<int> RL, vector<int> CL) {
    prefmaxc.resize(H * W);
    prefminc.resize(H * W);
    prefmaxr.resize(H * W);
    prefminr.resize(H * W);
    R.resize(H * W);
    C.resize(H * W);
    int maxc = -1;
    int minc = 1e9;
    int maxr = -1;
    int minr = 1e9;
    for (int i = 0; i < H * W; i++) {
        R[i] = RL[i];
        C[i] = CL[i];
    }
    for (int i = 0; i < H * W; i++) {
        maxc = max(maxc, C[i]);
        minc = min(minc, C[i]);
        maxr = max(maxr, R[i]);
        minr = min(minr, R[i]);
        prefmaxc[i] = maxc;
        prefminc[i] = minc;
        prefmaxr[i] = maxr;
        prefminr[i] = minr;
        if ((maxc - minc + 1) * (maxr - minr + 1) == i + 1) ans++;
    }
}

int swap_seats(int a, int b) {
    if (a > b) swap(a, b);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    for (int i = a; i < b; i++) {
        if ((prefmaxc[i] - prefminc[i] + 1) * (prefmaxr[i] - prefminr[i] + 1) == i + 1) ans--;
    }
    int maxc = a? prefmaxc[a - 1]: -1;
    int minc = a? prefminc[a - 1]: 1e9;
    int maxr = a? prefmaxr[a - 1]: -1;
    int minr = a? prefminr[a - 1]: 1e9;
    for (int i = a; i < b; i++) {
        maxc = max(maxc, C[i]);
        minc = min(minc, C[i]);
        maxr = max(maxr, R[i]);
        minr = min(minr, R[i]);
        prefmaxc[i] = maxc;
        prefminc[i] = minc;
        prefmaxr[i] = maxr;
        prefminr[i] = minr;
        if ((maxc - minc + 1) * (maxr - minr + 1) == i + 1) ans++;
    }
    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