Submission #829280

#	Time	Username	Problem	Language	Result	Execution time	Memory
829280		tranxuanbach	Seats (IOI18_seats)	C++17	17 / 100	4088 ms	110156 KiB

seats

#include "seats.h"

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

constexpr int inf = 1e9 + 7;

struct bounding_rectangle{
	int lx = inf, rx = -inf, ly = inf, ry = -inf;

	void insert(int x, int y){
		lx = min(lx, x);
		rx = max(rx, x);
		ly = min(ly, y);
		ry = max(ry, y);
	}

	int area(){
		return (rx - lx + 1) * (ry - ly + 1);
	}
};

int n, m;
vector <vector <int>> a;

vector <pair <int, int>> pos;

int ans;
vector <bounding_rectangle> b;

void give_initial_chart(int _n, int _m, vector <int> _r, vector <int> _c){
	n = _n;
	m = _m;
	a.assign(n, vector <int>(m));
	pos.resize(n * m);
	for (int val = 0; val < n * m; val++){
		int x = _r[val], y = _c[val];
		a[x][y] = val;
		pos[val] = pair{x, y};
	}

	ans = 0;
	b.resize(n * m + 1);
	for (int val = 0; val < n * m; val++){
		b[val + 1] = b[val];
		b[val + 1].insert(pos[val].first, pos[val].second);
		if (b[val + 1].area() == val + 1){
			ans++;
		}
	}
}

int swap_seats(int val1, int val2){
	if (val1 > val2){
		swap(val1, val2);
	}
	{
		auto [x1, y1] = pos[val1];
		auto [x2, y2] = pos[val2];
		swap(a[x1][y1], a[x2][y2]);
		swap(pos[val1], pos[val2]);
	}
	for (int val = val1; val < val2; val++){
		if (b[val + 1].area() == val + 1){
			ans--;
		}
		b[val + 1] = b[val];
		b[val + 1].insert(pos[val].first, pos[val].second);
		if (b[val + 1].area() == val + 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