Submission #409998

#	Time	Username	Problem	Language	Result	Execution time	Memory
409998		luciocf	Seats (IOI18_seats)	C++14	11 / 100	4094 ms	57416 KiB

seats

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

using namespace std;

const int maxn = 1e3+10;

int n, m;

vector<int> x, y;

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

	void build(int node, int l, int r, int q)
	{
		if (l == r)
		{
			if (!q) tree[0][node] = tree[1][node] = x[l];
			else tree[0][node] = tree[1][node] = y[l];

			return;
		}

		int mid = (l+r)>>1;

		build(2*node, l, mid, q); build(2*node+1, mid+1, r, q);

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

	void upd(int node, int l, int r, int pos, int v)
	{
		if (l == r)
		{
			tree[0][node] = tree[1][node] = v;
			return;
		}

		int mid = (l+r)>>1;

		if (pos <= mid) upd(2*node, l, mid, pos, v);
		else upd(2*node+1, mid+1, r, pos, v);

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

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

		int mid = (l+r)>>1;

		int p1 = query(2*node, l, mid, a, b, q);
		int p2 = query(2*node+1, mid+1, r, a, b, q);

		if (!q) return min(p1, p2);
		return max(p1, p2);
	}
} seg_x, seg_y;

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

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

	seg_x.build(1, 0, n*m-1, 0); seg_y.build(1, 0, n*m-1, 1);
}

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 ans = 0;

	for (int i = 0; i < n*m; )
	{
		int mn_x = seg_x.query(1, 0, n*m-1, 0, i, 0);
		int mx_x = seg_x.query(1, 0, n*m-1, 0, i, 1);

		int mn_y = seg_y.query(1, 0, n*m-1, 0, i, 0);
		int mx_y = seg_y.query(1, 0, n*m-1, 0, i, 1);

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

		i = max(i+1, (mx_x-mn_x+1)*(mx_y-mn_y+1)-1);
	}

	return ans;
}

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

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

	seg_x.upd(1, 0, n*m-1, a, x[a]); seg_x.upd(1, 0, n*m-1, b, x[b]);
	seg_y.upd(1, 0, n*m-1, a, y[a]); seg_y.upd(1, 0, n*m-1, b, y[b]);

	if (n <= 1000 && m <= 1000) return sub_2();
	return sub_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