Submission #829311

#	Time	Username	Problem	Language	Result	Execution time	Memory
829311		tranxuanbach	Seats (IOI18_seats)	C++17	25 / 100	4089 ms	73544 KiB

seats

#include "seats.h"

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

constexpr int inf = 1e9 + 7;

struct segment_tree{
	static pair <int, int> merge(const pair <int, int>& lhs, const pair <int, int>& rhs){
		return pair{min(lhs.first, rhs.first), max(lhs.second, rhs.second)};
	}

	static constexpr auto unit = pair{inf, -inf};
	vector <pair <int, int>> seg;

	segment_tree(){ }

	segment_tree(int n){
		int sz = 1;
		while (sz < n * 2){
			sz *= 2;
		}
		seg.assign(sz, unit);
	}

	void build(int id, int l, int r, const vector <int>& a){
		if (l == r){
			seg[id] = pair{a[l], a[l]};
			return;
		}
		int mid = (l + r) >> 1;
		build(id * 2, l, mid, a);
		build(id * 2 + 1, mid + 1, r, a);
		seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
	}

	void update(int id, int l, int r, int i, int x){
		if (l == r){
			seg[id] = pair{x, x};
			return;
		}
		int mid = (l + r) >> 1;
		if (i <= mid){
			update(id * 2, l, mid, i, x);
		}
		else{
			update(id * 2 + 1, mid + 1, r, i, x);
		}
		seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
	}

	pair <int, int> query(int id, int l, int r, int u, int v){
		if (v < l or r < u){
			return unit;
		}
		if (u <= l and r <= v){
			return seg[id];
		}
		int mid = (l + r) >> 1;
		return merge(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
	}
};

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 <int> pos_x, pos_y;

segment_tree seg_x, seg_y;

void give_initial_chart(int _n, int _m, vector <int> _r, vector <int> _c){
	n = _n;
	m = _m;
	pos_x.resize(n * m);
	pos_y.resize(n * m);
	for (int val = 0; val < n * m; val++){
		int x = _r[val], y = _c[val];
		pos_x[val] = x;
		pos_y[val] = y;
	}
	seg_x = segment_tree(n * m);
	seg_x.build(1, 0, n * m - 1, pos_x);
	seg_y = segment_tree(n * m);
	seg_y.build(1, 0, n * m - 1, pos_y);
}

int swap_seats(int val1, int val2){
	{
		int x1 = pos_x[val1], x2 = pos_x[val2];
		swap(pos_x[val1], pos_x[val2]);
		int y1 = pos_y[val1], y2 = pos_y[val2];
		swap(pos_y[val1], pos_y[val2]);
		seg_x.update(1, 0, n * m - 1, val1, x2);
		seg_x.update(1, 0, n * m - 1, val2, x1);
		seg_y.update(1, 0, n * m - 1, val1, y2);
		seg_y.update(1, 0, n * m - 1, val2, y1);
	}
	int ans = 0;
	int ptr = 0;
	while (ptr < n * m){
		auto [lx, rx] = seg_x.query(1, 0, n * m - 1, 0, ptr);
		auto [ly, ry] = seg_y.query(1, 0, n * m - 1, 0, ptr);
		if ((rx - lx + 1) * (ry - ly + 1) == ptr + 1){
			ans++;
			ptr++;
		}
		else{
			ptr = (rx - lx + 1) * (ry - ly + 1) - 1;
		}
	}
	return ans;
}

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