Submission #769176

#	Time	Username	Problem	Language	Result	Execution time	Memory
769176		pashka	Seats (IOI18_seats)	C++14	11 / 100	4057 ms	56484 KiB

seats

#include "seats.h"

using namespace std;

int n, m;
vector<int> x;
vector<int> y;

int res;
vector<int> minx, maxx, miny, maxy;
vector<bool> pr;

void recalc() {
    minx[0] = n - 1;
    maxx[0] = 0;
    miny[0] = m - 1;
    maxy[0] = 0;
    for (int i = 0; i < n * m; i++) {
        minx[i + 1] = min(minx[i], x[i]);
        maxx[i + 1] = max(maxx[i], x[i]);
        miny[i + 1] = min(miny[i], y[i]);
        maxy[i + 1] = max(maxy[i], y[i]);
    }
    for (int i = 1; i <= n * m; i++) {
        pr[i] = ((maxx[i] - minx[i] + 1) * (maxy[i] - miny[i] + 1) == i);
    }
    res = 0;
    for (int i = 0; i < n * m; i++) {
        res += pr[i + 1];
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    x = R;
    y = C;
    n = H;
    m = W;
    minx.resize(n * m + 1);
    maxx.resize(n * m + 1);
    miny.resize(n * m + 1);
    maxy.resize(n * m + 1);
    pr.resize(n * m + 1);
    recalc();
}


int swap_seats(int a, int b) {
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    recalc();
    return res;
}

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