Submission #596546

#	Time	Username	Problem	Language	Result	Execution time	Memory
596546		AlperenT	Seats (IOI18_seats)	C++17	0 / 100	4002 ms	39480 KiB

seats

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

using namespace std;

const int N = 1e6 + 5, INF = 1e9 + 5;

int n, h, w, ans;

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    return {min(a.first, b.first), max(a.second, b.second)};
}

vector<int> X, Y;

pair<int, int> xprefix[N], yprefix[N];

void give_initial_chart(int H, int W, vector<int> X_, vector<int> Y_) {
    X = X_, Y = Y_;

    X.insert(X.begin(), -1);
    Y.insert(Y.begin(), -1);

    n = H * W;

    xprefix[0] = {INF, -INF}, yprefix[0] = {INF, -INF};

    for(int i = 1; i <= n; i++) xprefix[i] = merge(xprefix[i - 1], {X[i], X[i]});
    for(int i = 1; i <= n; i++) yprefix[i] = merge(yprefix[i - 1], {Y[i], Y[i]});

    for(int i = 1; i <= n; i++) if((xprefix[i].second - xprefix[i].first + 1) * (yprefix[i].second - yprefix[i].first + 1) == i) ans++;
}

int swap_seats(int a, int b){
    a++, b++;

    swap(X[a], X[b]);
    swap(Y[a], Y[b]);

    for(int i = a; i <= b; i++){
        if((xprefix[i].second - xprefix[i].first + 1) * (yprefix[i].second - yprefix[i].first + 1) == i) ans--;

        xprefix[i] = merge(xprefix[i - 1], {X[i], X[i]});
        yprefix[i] = merge(yprefix[i - 1], {Y[i], Y[i]});

        if((xprefix[i].second - xprefix[i].first + 1) * (yprefix[i].second - yprefix[i].first + 1) == i) ans++;
    }

    return ans;
}

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