Submission #413995

#	Time	Username	Problem	Language	Result	Execution time	Memory
413995		_fractal	Seats (IOI18_seats)	C++14	70 / 100	4045 ms	181520 KiB

seats

#include "seats.h"
#include <iostream>
#include <climits>
using namespace std;
 
#define pb push_back
#define S second
#define F first
 
typedef pair<int, int> pii;
 
const int N = 2e6 + 200;
const int inf = (1 << 30);
 
int S, ans = 0;
int H, W;
pair<int, int> pos[N], act[N];
int rx[N], lx[N], ry[N], ly[N], val[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) {
		cnt[v] = tr - tl + 1;
		if (tl == tr) return;
		int tm = tl + tr >> 1;
		build(v * 2, tl, tm);
		build(v * 2 + 1, tm + 1, tr);
	}

	void out(int v = 1, int tl = 1, int tr = S) {
		push(v, tl, tr);
		if (tl == tr) {
			cerr << t[v] << " ";
			return;
		}
		int tm = tl + tr >> 1;
		out(v * 2, tl, tm);
		out(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];
	}

	void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = S) {
		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() {
		push(1, 1, S);
		return cnt[1];
	}
} tt;

struct tree {
	pii t[N << 2];
	int SZ;
 
	void upd(int v, int val) {
		v = v + SZ - 1;
		t[v] = {val, val};
		if (val == inf)
			t[v].F *= -1;
		v >>= 1;
		while (v) {
			t[v].F = max(t[v * 2].F, t[v * 2 + 1].F);
			t[v].S = min(t[v * 2].S, t[v * 2 + 1].S);
			v >>= 1;
		}
	}
 
	pii get(int l, int r) {
		l = l + SZ - 1;
		r = r + SZ - 1;
		pii ans = {-inf, +inf};
		while (true) {
			if (l % 2 == 1) {
				ans.F = max(ans.F, t[l].F);
				ans.S = min(ans.S, t[l].S);
			}
			if (r % 2 == 0) {
				ans.F = max(ans.F, t[r].F);
				ans.S = min(ans.S, t[r].S);
			}
			if (l == r)
				break;
			l = (l + 1) >> 1;
			r = (r - 1) >> 1;
		}
		return ans;
	}
} tx, ty;
 
void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
	H = _H, W = _W;
	S = H * W;
	for (int i = 0; i < H * W; ++i) {
		pos[i + 1] = {R[i] + 1, C[i] + 1};
		val[C[i] + 1] = i + 1;
	}
	if (H == 1) {
		tt.build();
		val[0] = S + 1;
		val[S + 1] = S + 1;
		for (int i = 1; i <= S + 1; ++i) {
			tt.upd(min(val[i - 1], val[i]), max(val[i - 1], val[i]) - 1, 1);
		}
		return;
	}
	if (H <= 1000 && W <= 1000) {
		tx.SZ = 1;
		while (tx.SZ < S)
			tx.SZ <<= 1;
		ty.SZ = tx.SZ;
		for (int i = 1; i <= tx.SZ; ++i) {
			if (i > S) {
				tx.upd(i, +inf);
				ty.upd(i, +inf);
			}
			else {
				tx.upd(i, pos[i].F);
				ty.upd(i, pos[i].S);
			}
		}
		return;
	}
	rx[0] = -inf, lx[0] = +inf;
	ry[0] = -inf, ly[0] = +inf;
	for (int i = 1; i <= S; ++i) {
		rx[i] = max(rx[i - 1], pos[i].F);
		lx[i] = min(lx[i - 1], pos[i].F);
		ry[i] = max(ry[i - 1], pos[i].S);
		ly[i] = min(ly[i - 1], pos[i].S);
		if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
			ans++;
	}
	return;
}
 
int get(int pos) {
	pair<int, int> a = tx.get(1, pos);
	pair<int, int> b = ty.get(1, pos);
	return (a.F - a.S + 1) * 1LL * (b.F - b.S + 1);
}

void del(int pos, bool c = 0) {
	if (!c)
		tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, -1);
	pos++;
	tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, -1);
}

void add(int pos, bool c = 0) {
	if (!c)
		tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, +1);
	pos++;
	tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, +1);
}
 
int swap_seats(int a, int b) {
	++a, ++b;
	if (a > b)
		swap(a, b);
	if (H == 1) {
		if (pos[a].S > pos[b].S) swap(a, b);
		del(pos[a].S);
		if (pos[a].S + 1 < pos[b].S)
			del(pos[b].S);
		else
			del(pos[b].S, 1);
	}
	swap(pos[a], pos[b]);
	val[pos[a].S] = a;
	val[pos[b].S] = b;
	if (H == 1) {
		a = pos[a].S, b = pos[b].S;
		if (a > b) swap(a, b);
		add(a);
		if (a + 1 < b)
			add(b);
		else
			add(b, 1);
		return tt.get();
	}
	if (H <= 1000 && W <= 1000) {
		tx.upd(a, pos[a].F);
		tx.upd(b, pos[b].F);
		ty.upd(a, pos[a].S);
		ty.upd(b, pos[b].S);
		int pos = 1, cnt = 0;
		while (true) {
			int npos = get(pos);
			if (npos == pos) {
				cnt++;
			}
			pos = npos + (pos == npos);
			if (pos > S) break;
		}
		return cnt;
	}
	for (int i = a; i <= b; ++i) {
		if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
			ans--;
		rx[i] = max(rx[i - 1], pos[i].F);
		lx[i] = min(lx[i - 1], pos[i].F);
		ry[i] = max(ry[i - 1], pos[i].S);
		ly[i] = min(ly[i - 1], pos[i].S);
		if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
			ans++;
	}
	return ans;
}

Compilation message (stderr)

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