Submission #1190027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190027		MatteoArcari	Seats (IOI18_seats)	C++20	0 / 100	4097 ms	51704 KiB

seats

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

vector<int> r, c;
vector<vector<int>> mat;
vector<int> memo;
vector<int> mup, mdown, mleft, mright, mma;
int n, m, ans = 1;

void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
    r = _r; c = _c;
    n = _n; m = _m;
    mat.resize(n, vector<int>(m));
    for (int i = 0; i < n * m; i++) {
        mat[r[i]][c[i]] = i;
    }
    memo.resize(n * m);
    memo[0] = 1;
    int up = r[0], down = r[0];
    int left = c[0], right = c[0];

    int ma = 0;
    
    for (int i = 0; i < n * m; i++) {
        bool flag = 0;
        while (up > r[i]) {
            up--; flag = 1;
            for (int j = left; j <= right; j++) ma = max(ma, mat[up][j]); 
        }
        while (down < r[i]) {
            down++; flag = 1;
            for (int j = left; j <= right; j++) ma = max(ma, mat[down][j]);
        }
        while (left > c[i]) {
            left--; flag = 1;
            for (int j = up; j <= down; j++) ma = max(ma, mat[j][left]);
        }
        while (right < c[i]) {
            right++; flag = 1;
            for (int j = up; j <= down; j++) ma = max(ma, mat[j][right]);
        }
        int dim = (down - up + 1) * (right - left + 1);
        if (flag && ma == dim - 1) {
            ans++;
            memo[i] = 1;
        }
        mup.push_back(up);
        mdown.push_back(down);
        mleft.push_back(left);
        mright.push_back(right);
        mma.push_back(ma);
    }
}

int swap_seats(int a, int b) {
    if (a > b) swap(a, b);
    
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);

    int up = r[0], down = r[0];
    int left = c[0], right = c[0];
    int ma = 0;

    if (!a) a++;
    
    up = mup[a - 1];
    down = mdown[a - 1];
    left = mleft[a - 1];
    right = mright[a - 1];
    ma = mma[a - 1];

    
    for (int i = a; i <= b; i++) {
        bool flag = 0;
        while (up > r[i]) {
            up--; flag = 1;
            for (int j = left; j <= right; j++) ma = max(ma, mat[up][j]); 
        }
        while (down < r[i]) {
            down++; flag = 1;
            for (int j = left; j <= right; j++) ma = max(ma, mat[down][j]);
        }
        while (left > c[i]) {
            left--; flag = 1;
            for (int j = up; j <= down; j++) ma = max(ma, mat[j][left]);
        }
        while (right < c[i]) {
            right++; flag = 1;
            for (int j = up; j <= down; j++) ma = max(ma, mat[j][right]);
        }
        ans -= memo[i];
        memo[i] = 0;
        int dim = (down - up + 1) * (right - left + 1);
        if (flag && ma == dim - 1) memo[i] = 1;
        ans += memo[i];
        mup[i] = up;
        mdown[i] = down;
        mleft[i] = left;
        mright[i] = right;
        mma[i] = ma;
    }
    
    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