Submission #409971

#	Time	Username	Problem	Language	Result	Execution time	Memory
409971		luciocf	Seats (IOI18_seats)	C++14	0 / 100	4091 ms	174040 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

using namespace std;

const int maxn = 1e3+10;

int n, m;

struct SegmentTree2d
{
	int tree[2][4*maxn][4*maxn];

	void upd_y(int nodex, int lx, int rx, int nodey, int ly, int ry, int posy, int v)
	{
		if (ly == ry)
		{
			if (lx == rx) tree[0][nodex][nodey] = tree[1][nodex][nodey] = v;
			else
			{
				tree[0][nodex][nodey] = max(tree[0][2*nodex][nodey], tree[0][2*nodex+1][nodey]);
				tree[1][nodex][nodey] = min(tree[1][2*nodex][nodey], tree[1][2*nodex+1][nodey]);
			}
			return;
		}

		int mid = (ly+ry)/2;

		if (posy <= mid) upd_y(nodex, lx, rx, 2*nodey, ly, mid, posy, v);
		else upd_y(nodex, lx, rx, 2*nodey+1, mid+1, ry, posy, v);

		tree[0][nodex][nodey] = max(tree[0][2*nodex][nodey], tree[0][2*nodex+1][nodey]);
		tree[1][nodex][nodey] = min(tree[1][2*nodex][nodey], tree[1][2*nodex+1][nodey]);
	}

	void upd_x(int nodex, int lx, int rx, int posx, int posy, int v)
	{
		if (lx == rx)
		{
			upd_y(nodex, lx, rx, 1, 0, m-1, posy, v);
			return;
		}

		int mid = (lx+rx)/2;

		if (posx <= mid) upd_x(2*nodex, lx, mid, posx, posy, v);
		else upd_x(2*nodex+1, mid+1, rx, posx, posy, v);

		upd_y(nodex, lx, rx, 1, 0, m-1, posy, v);
	}

	int query_y(int nodex, int nodey, int l, int r, int a, int b, int q)
	{
		if (l > b || r < a) return (q == 0 ? 0 : n*m);
		if (l >= a && r <= b) return tree[q][nodex][nodey];

		int mid = (l+r)/2;

		int p1 = query_y(nodex, 2*nodey, l, mid, a, b, q);
		int p2 = query_y(nodex, 2*nodey+1, mid+1, r, a, b, q);
		
		if (!q) return max(p1, p2);
		return min(p1, p2);
	}

	int query_x(int nodex, int l, int r, int ax, int bx, int ay, int by, int q)
	{
		if (l > bx || r < ax) return (q == 0 ? 0 : n*m);
		if (l >= ax && r <= bx) return query_y(nodex, 1, 0, m-1, ay, by, q);

		int mid = (l+r)/2;

		int p1 = query_x(2*nodex, l, mid, ax, bx, ay, by, q);
		int p2 = query_x(2*nodex+1, mid+1, r, ax, bx, ay, by, q);
		
		if (!q) return max(p1, p2);
		return min(p1, p2);
	}
} seg;

vector<int> x, y;

int tab[maxn][maxn];

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	n = H, m = W;

	for (int i = 0; i < 4*n; i++)
		for (int j = 0; j < 4*m; j++)
			seg.tree[1][i][j] = n*m;

	for (int i = 0; i < n*m; i++)
	{
		x.push_back(R[i]);
		y.push_back(C[i]);

		tab[R[i]][C[i]] = i;
		seg.upd_x(1, 0, n-1, R[i], C[i], i);
	}
}

int sub_1(void)
{	
	int mn_x = x[0], mx_x = x[0];
	int mn_y = y[0], mx_y = y[0];
	int ans = 1;

	for (int i = 1; i < n*m; i++)
	{
		mn_x = min(mn_x, x[i]); mx_x = max(mx_x, x[i]);
		mn_y = min(mn_y, y[i]); mx_y = max(mx_y, y[i]);

		if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1) ans++;
	}

	return ans;
}

int sub_2(void)
{
	int mn_x = x[0], mx_x = x[0];
	int mn_y = y[0], mx_y = y[0];
	int ans = 0;

	while (true)
	{
		int mx = seg.query_x(1, 0, n-1, mn_x, mx_x, mn_y, mx_y, 0)+1;

		if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == mx) ans++;
		if ((mn_x == 0 && mx_x == n-1 && mn_y == 0 && mx_y == m-1) || mx == n*m) break;

		int prox = n*m;
 
		if (mn_x > 0) prox = min(prox, seg.query_x(1, 0, n-1, 0, mn_x-1, 0, m-1, 1));
		if (mn_y > 0) prox = min(prox, seg.query_x(1, 0, n-1, 0, n-1, 0, mn_y-1, 1));
 
		if (mx_x < n-1) prox = min(prox, seg.query_x(1, 0, n-1, mx_x+1, n-1, 0, m-1, 1));
		if (mx_y < m-1) prox = min(prox, seg.query_x(1, 0, n-1, 0, n-1, mx_y+1, m-1, 1));
 
		mn_x = min(mn_x, x[prox]); mx_x = max(mx_x, x[prox]);
		mn_y = min(mn_y, y[prox]); mx_y = max(mx_y, y[prox]);
	}

	return ans;
}

int swap_seats(int a, int b)
{
	int xa = x[a], ya = y[a];
	int xb = x[b], yb = y[b];

	swap(tab[xa][ya], tab[xb][yb]);
	seg.upd_x(1, 0, n-1, xa, ya, tab[xa][ya]);
	seg.upd_x(1, 0, n-1, xb, yb, tab[xb][yb]);

	x[a] = xb, y[a] = yb;
	x[b] = xa, y[b] = ya;

	if (n <= 1000 && m <= 1000) return sub_2();
	return sub_1();
}

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