Submission #413670

#	Time	Username	Problem	Language	Result	Execution time	Memory
413670		_fractal	Seats (IOI18_seats)	C++14	11 / 100	4088 ms	71916 KiB

seats

#include "seats.h"
#include <climits>
using namespace std;

#define pb push_back
#define S second
#define F first

typedef pair<short int, short int> pii;

const int N = 1e6 + 200;
const int inf = (1 << 30);

int S, ans = 0;
int H, W;

pair<int, int> pos[N];
int rx[N], lx[N], ry[N], ly[N];

struct tree {

	pii t[N << 2];

	void merge(pii &a, pii b, pii c) {
		a.F = max(b.F, c.F);
		a.S = min(b.S, c.S);
	}

	void upd(int pos, int val, int v = 1, int tl = 1, int tr = S) {
		if (tl == tr) {
			t[v] = {val, val};
			return;
		}
		int tm = tl + tr >> 1;
		if (pos <= tm)
			upd(pos, val, v * 2, tl, tm);
		else
			upd(pos, val, v * 2 + 1, tm + 1, tr);
		merge(t[v], t[v * 2], t[v * 2 + 1]);
	};

	pii get(int l, int r, int v = 1, int tl = 1, int tr = S) {
		if (l <= tl && tr <= r)
			return t[v];
		if (r < tl || tr < l)
			return {SHRT_MIN, SHRT_MAX};
		int tm = tl + tr >> 1;
		pii ret;
		merge(ret, get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
		return ret;
	}
} tx, ty;

void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
	H = _H, W = _W;
	S = H * W;
	swap(R, C);
	for (int i = 0; i < H * W; ++i)
		pos[i + 1] = {R[i], C[i]};
	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 (H + W <= 3000) {
			tx.upd(i, pos[i].F);
			ty.upd(i, pos[i].S);
		}
		if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i)
			ans++;
	}
}

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) * (b.F - b.S + 1);
}

int swap_seats(int a, int b) {
	++a, ++b;
	if (a > b) swap(a, b);
	swap(pos[a], pos[b]);
	if (H + W <= 3000) {
		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::upd(int, int, int, int, int)':
seats.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
seats.cpp: In member function 'pii tree::get(int, int, int, int, int)':
seats.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

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