Submission #116051

#	Time	Username	Problem	Language	Result	Execution time	Memory
116051		roseanne_pcy	Seats (IOI18_seats)	C++14	100 / 100	1785 ms	141688 KiB

seats

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e6+5;

int n, m;

int tot;

int r[maxn];

struct node
{
	int val, cnt, lz;
	node(int a = 0, int b = 0) : val(a), cnt(b)
	{
		lz = 0;
	}
};

node st[4*maxn];

node pull(node &x, node &y)
{
	if(x.val< y.val) return x;
	if(x.val> y.val) return y;
	return node(x.val, x.cnt+y.cnt);
}

void pushdown(int p, int L, int R)
{
	if(st[p].lz == 0) return;
	st[p].val += st[p].lz;
	if(L != R)
	{
		st[2*p].lz += st[p].lz;
		st[2*p+1].lz += st[p].lz;
	}
	st[p].lz = 0;
}

void build(int p = 1, int L = 0, int R = tot-1)
{
	if(L == R)
	{
		st[p] = node(0, 1);
		return;
	}
	int M = (L+R)/2;
	build(2*p, L, M);
	build(2*p+1, M+1, R);
	st[p] = pull(st[2*p], st[2*p+1]);
}

void update(int i, int j, int dx, int p = 1, int L = 0, int R = tot-1)
{
	pushdown(p, L, R);
	if(i> j || i> R || j< L) return;
	if(i<= L && R<= j) 
	{
		st[p].lz += dx;
		pushdown(p, L, R);
		return;
	}
	int M = (L+R)/2;
	update(i, j, dx, 2*p, L, M);
	update(i, j, dx, 2*p+1, M+1, R);
	st[p] = pull(st[2*p], st[2*p+1]);
}

node ask(int i, int j, int p = 1, int L = 0, int R = tot-1)
{
	if(i> R || j< L) return node(1e9, 0);
	pushdown(p, L, R);
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	node x = ask(i, j, 2*p, L, M);
	node y = ask(i, j, 2*p+1, M+1, R);
	return pull(x, y);
}

vector< vector<int> > bow;

int row[maxn];
int col[maxn];

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void add(int x, int y, int a, int b)
{
	// printf("add %d to [%d %d]\n", val, a, b);
	for(int base = 0; base< 8; base += 2)
	{
		vector<int> t;
		for(int pp = base; pp<= base+2; pp++)
		{
			int pos = pp%8;
			// printf("%d ", pos);
			int loc = 1e9;
			if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
			{
				loc = bow[x+dx[pos]][y+dy[pos]];
			}
			t.pb(loc);
		}
		// printf("\n");
		sort(t.begin(), t.end());
		int t0 = t[0], t1 = t[1], t2 = t[2];
		// printf("%d %d %d\n", t0, t1, t2);
		update(a, min(t0-1, b), 1);
		update(max(a, t0), min(t1-1, b), -1);
		update(max(a, t1), min(t2-1, b), 1);
		update(max(a, t2), b, -1);
	}
}

void rem(int x, int y, int a, int b)
{
	for(int base = 0; base< 8; base += 2)
	{
		vector<int> t;
		for(int pp = base; pp<= base+2; pp++)
		{
			int pos = pp%8;
			int loc = 1e9;
			if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
			{
				loc = bow[x+dx[pos]][y+dy[pos]];
			}
			t.pb(loc);
		}
		sort(t.begin(), t.end());
		int t0 = t[0], t1 = t[1], t2 = t[2];
		// printf("%d %d %d\n", t0, t1, t2);
		update(a, min(t0-1, b), -1);
		update(max(a, t0), min(t1-1, b), 1);
		update(max(a, t1), min(t2-1, b), -1);
		update(max(a, t2), b, 1);
	}
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	n = H; m = W;
	tot = n*m;
	bow.assign(n, vector<int>(m));
	build();
	int prv = 0;
	for(int i = 0; i< tot; i++)
	{
		bow[R[i]][C[i]] = i;
		row[i] = R[i];
		col[i] = C[i];
	}
	for(int i = 0; i< tot; i++)
	{
		int cur = prv;
		for(int base = 0; base< 8; base += 2)
		{
			int cnt = 0;
			for(int pp = base; pp<= base+2; pp++)
			{
				int pos = pp%8;
				int loc = 0;
				int x = row[i], y = col[i];
				if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
				{
					loc = bow[x+dx[pos]][y+dy[pos]]< i;
				}
				cnt += loc;
			}
			if(cnt == 1 || cnt == 3) cur--;
			else cur++;
		}
		update(i, i, cur);
		// printf("f[%d] = %d\n", i, cur);
		prv = cur;
	}
	// printf("(%d, %d)\n", kk.val, kk.cnt);
}

int swap_seats(int a, int b)
{
	if(a> b) swap(a, b);
	rem(row[a], col[a], a, b-1);
	// printf("finished reming\n");
	// printf("f' = ");
	// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
	// printf("\n");
	swap(bow[row[a]][col[a]], bow[row[b]][col[b]]);
	add(row[b], col[b], a, b-1);
	swap(row[a], row[b]);
	swap(col[a], col[b]);
	node kk = ask(0, tot-1);
	// printf("f = ");
	// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
	// printf("\n");
	// printf("(%d, %d)\n", kk.val, kk.cnt);
	if(kk.val == 4) return kk.cnt;
	return 0;
}

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