Submission #414617

#	Time	Username	Problem	Language	Result	Execution time	Memory
414617		_fractal	Seats (IOI18_seats)	C++17	100 / 100	2464 ms	128608 KiB

seats

#include "seats.h"
#include <iostream>
#include <climits>
#include <algorithm>
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;
int cur[4];
int **val, **was;
int dd[n];
pii pos[n];

struct tree_line {
	int t[n << 2], p[n << 2];
	int cnt[n << 2];

	void push(int v, int tl, int tr) {
		if (p[v] != 0) {
			if (tl != tr) {
				p[v * 2] += p[v];
				p[v * 2 + 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] = dd[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) {
		if (l > r) return;
		push(v, tl, tr);
		if (l <= tl && tr <= r) {
			p[v] += val;
			push(v, tl, tr);
			return;
		}
		if (r < tl || tr < l)
			return;
		int tm = tl + tr >> 1;
		upd(l, r, val, v * 2, tl, tm);
		upd(l, r, val, v * 2 + 1, tm + 1, tr);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
		cnt[v] = 0;
		if (t[v] == t[v * 2])
			cnt[v] += cnt[v * 2];
		if (t[v] == t[v * 2 + 1])
			cnt[v] += cnt[v * 2 + 1];
	}

	int get() {
		return cnt[1];
	}
} t;
 
void del(int _x, int _y) {
	for (int j = 0, x, y; j < 4; ++j) {
		x = _x - dx[j];
		y = _y - dy[j];
		if (was[x][y]) continue;
		was[x][y] = 1;
		for (int i = 0; i < 4; ++i)
			cur[i] = val[x + dx[i]][y + dy[i]];
		sort(cur, cur + 4);
		t.upd(cur[0], cur[1] - 1, -1);
		t.upd(cur[2], cur[3] - 1, -5);
	}
}

void add(int _x, int _y) {
	for (int j = 0, x, y; j < 4; ++j) {
		x = _x - dx[j];
		y = _y - dy[j];
		if (was[x][y]) continue;
		was[x][y] = 1;
		for (int i = 0; i < 4; ++i)
			cur[i] = val[x + dx[i]][y + dy[i]];
		sort(cur, cur + 4);
		t.upd(cur[0], cur[1] - 1, +1);
		t.upd(cur[2], cur[3] - 1, +5);
	}
}

void clr(int _x, int _y) {
	for (int j = 0, x, y; j < 4; ++j) {
		x = _x - dx[j];
		y = _y - dy[j];
		was[x][y] = 0;
	}
}

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];
	was = new int*[h + 5];
	for (int i = 0; i <= h + 3; ++i) {
		val[i] = new int[w + 5];
		was[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) {
			clr(i, j);
			for (int k = 0; k < 4; ++k)
				cur[k] = val[i + dx[k]][j + dy[k]];
			sort(cur, cur + 4);
			dd[cur[0]] += 1;
			dd[cur[1]] -= 1;
			dd[cur[2]] += 5;
			dd[cur[3]] -= 5;
		}
	}
	for (int i = 1; i <= s; ++i)
		dd[i] += dd[i - 1];
	t.build();
	return;
}
 
int swap_seats(int a, int b) {
	++a, ++b;
	del(pos[a].f, pos[a].s);
	del(pos[b].f, pos[b].s);
	clr(pos[a].f, pos[a].s);
	clr(pos[b].f, pos[b].s);
	swap(pos[a], pos[b]);
	val[pos[a].f][pos[a].s] = a;
	val[pos[b].f][pos[b].s] = b;
	add(pos[a].f, pos[a].s);
	add(pos[b].f, pos[b].s);
	clr(pos[a].f, pos[a].s);
	clr(pos[b].f, pos[b].s);
	return t.get();
}

Compilation message (stderr)

seats.cpp: In member function 'void tree_line::build(int, int, int)':
seats.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
seats.cpp: In member function 'void tree_line::upd(int, int, int, int, int, int)':
seats.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   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