Submission #414610

#	Time	Username	Problem	Language	Result	Execution time	Memory
414610		_fractal	Seats (IOI18_seats)	C++17	100 / 100	2389 ms	89572 KiB

seats

#include "seats.h"
#include <iostream>
#include <climits>
#include <algorithm>
#include <tuple>
using namespace std;
 
#define pb push_back
#define S second
#define F first
 
typedef pair<int, int> pii;
 
const int N = 1e6 + 200;
const int inf = (1 << 30);

const int dx[] = {0, 1, 0, 1};
const int dy[] = {0, 0, 1, 1};
 
int S, ans = 0;
int H, W;
vector<int> cur;
vector<pair<int, int>> is;
int **val;
pii pos[N];

int t[N << 2], p[N << 2];
int cnt[N << 2], add[N];

inline void push(int v, int tl, int tr) {
	if (tl != tr) {
		p[v << 1] += p[v];
		p[v << 1 | 1] += p[v];
	}
	t[v] += p[v];
	p[v] = 0;
}

void build(int v = 1, int tl = 1, int tr = S) {
	if (tl == tr) {
		t[v] = add[tl];
		cnt[v] = 1;
		return;
	}
	int tm = tl + tr >> 1;
	build(v << 1, tl, tm);
	build(v << 1 | 1, tm + 1, tr);
	t[v] = min(t[v << 1], t[v << 1 | 1]);
	cnt[v] = 0;
	if (t[v] == t[v << 1])
		cnt[v] += cnt[v << 1];
	if (t[v] == t[v << 1 | 1])
		cnt[v] += cnt[v << 1 | 1];
}

void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = S) {
	push(v, tl, tr);
	if (r < tl || tr < l || l > r)
		return;
	if (l <= tl && tr <= r) {
		p[v] += val;
		push(v, tl, tr);
		return;
	}
	int tm = tl + tr >> 1;
	upd(l, r, val, v << 1, tl, tm);
	upd(l, r, val, v << 1 | 1, tm + 1, tr);
	t[v] = min(t[v << 1], t[v << 1 | 1]);
	cnt[v] = 0;
	if (t[v] == t[v << 1])
		cnt[v] += cnt[v << 1];
	if (t[v] == t[v << 1 | 1])
		cnt[v] += cnt[v << 1 | 1];
}

void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
	H = _H, W = _W;
	S = H * W;
	val = new int*[H + 5];
	for (int i = 0; i <= H + 3; ++i)
		val[i] = new int[W + 5];
	for (int i = 1; i <= S; ++i) {
		C[i - 1]++, R[i - 1]++;
		pos[i] = {R[i - 1], C[i - 1]};
		val[R[i - 1]][C[i - 1]] = i;
	}
	for (int i = 0; i <= W + 1; ++i)
		val[0][i] = val[H + 1][i] = S + 1;
	for (int i = 0; i <= H + 1; ++i)
		val[i][0] = val[i][W + 1] = S + 1;
	for (int i = 1; i <= H + 1; ++i) {
		for (int j = 1; j <= W + 1; ++j) {
			cur = {val[i][j], val[i - 1][j], val[i][j - 1], val[i - 1][j - 1]};
			sort(cur.begin(), cur.end());
			add[cur[0]] += 1;
			add[cur[1]] -= 1;
			add[cur[2]] += 5;
			add[cur[3]] -= 5;
		}
	}
	for (int i = 1; i <= S; ++i)
		add[i] += add[i - 1];
	build();
	return;
}
 
int swap_seats(int a, int b) {
	++a, ++b;
	is.clear();
	for (int i = 0; i < 4; ++i)
		is.pb({pos[a].F + dx[i], pos[a].S + dy[i]});
	for (int i = 0; i < 4; ++i)
		is.pb({pos[b].F + dx[i], pos[b].S + dy[i]});
	sort(is.begin(), is.end());
	is.erase(unique(is.begin(), is.end()), is.end());
	int i, j;
	for (auto it : is) {
		tie(i, j) = it;
		cur = {val[i][j], val[i - 1][j], val[i][j - 1], val[i - 1][j - 1]};
		sort(cur.begin(), cur.end());
		upd(cur[0], cur[1] - 1, -1);
		upd(cur[2], cur[3] - 1, -5);
	}
	swap(pos[a], pos[b]);
	swap(val[pos[a].F][pos[a].S], val[pos[b].F][pos[b].S]);
	for (auto it : is) {
		tie(i, j) = it;
		cur = {val[i][j], val[i - 1][j], val[i][j - 1], val[i - 1][j - 1]};
		sort(cur.begin(), cur.end());
		upd(cur[0], cur[1] - 1, +1);
		upd(cur[2], cur[3] - 1, +5);
	}
	return cnt[1];
}

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
seats.cpp: In function 'void upd(int, int, int, int, int, int)':
seats.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

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