Submission #76357

#	Time	Username	Problem	Language	Result	Execution time	Memory
76357		kriii	Seats (IOI18_seats)	C++17	100 / 100	1482 ms	54528 KiB

seats

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

const int Z = 1<<20;

struct node{
	node()
	{
		sum = min = 0; cnt = 1;
	}

	node(int v)
	{
		sum = min = v; cnt = 1;
	}

	int sum, min, cnt;

	node operator *(const node &t) const{
		node res;
		
		res.sum = sum + t.sum;

		if (min < sum + t.min) res.min = min;
		else res.min = sum + t.min;

		res.cnt = 0;
		if (res.min == min) res.cnt += cnt;
		if (res.min == sum + t.min) res.cnt += t.cnt;

		return res;
	}

	void add(int p)
	{
		sum += p;
		min += p;
	}
} IT[Z*2];

int N,A[1001001]; bool chk[1001001]; int H,W; vector<int> R,C;

void upd(int x)
{
	x /= 2;
	while (x){
		IT[x] = IT[x*2] * IT[x*2+1];
		x /= 2;
	}
}

set<int> ups;
void add(int i, int p, bool up = true)
{
	if (p > 0){
		if (chk[i]) return;
		chk[i] = 1;
	}
	else{
		if (!chk[i]) return;
		chk[i] = 0;
	}
	int x = R[i], y = C[i];
	int dx[5] = {0,1,0,-1,0};
	int dy[5] = {1,0,-1,0,1};
	for (int k=0;k<4;k++){
		int u[2];
		for (int d=0;d<2;d++){
			int px = x + dx[k+d];
			int py = y + dy[k+d];
			if (px < 0 || px >= H || py < 0 || py >= W) u[d] = N;
			else u[d] = A[px*W+py];
		}

		int s = N, e = 0;
		if (i < u[0] && i < u[1]){
			s = i + Z;
			e = min(u[0],u[1]) + Z;
		}

		if (u[0] < i && u[1] < i){
			s = max(u[0],u[1]) + Z;
			e = i + Z;
		}

		if (s < e){
			IT[s].add(+p);
			IT[e].add(-p);
			if (up){
				ups.insert(s);
				ups.insert(e);
			}
		}
	}
}

void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_)
{
	H = H_; W = W_; R = R_; C = C_; N = H * W;
	for (int i=0;i<N;i++) A[R[i]*W+C[i]] = i;
	IT[N+Z].add(10000);
	for (int i=0;i<N;i++) add(i,1,false);
	for (int i=Z-1;i>=1;i--) IT[i] = IT[i*2] * IT[i*2+1];
}

int swap_seats(int a, int b)
{
	int dx[5] = {0,1,0,-1,0};
	int dy[5] = {1,0,-1,0,0};
	for (int i : {a,b}) for (int k=0;k<5;k++){
		int x = R[i] + dx[k];
		int y = C[i] + dy[k];
		if (x < 0 || x >= H || y < 0 || y >= W) continue;
		add(A[x*W+y],-1);
	}

	swap(R[a],R[b]);
	swap(C[a],C[b]);
	A[R[a]*W+C[a]] = a;
	A[R[b]*W+C[b]] = b;

	for (int i : {a,b}) for (int k=0;k<5;k++){
		int x = R[i] + dx[k];
		int y = C[i] + dy[k];
		if (x < 0 || x >= H || y < 0 || y >= W) continue;
		add(A[x*W+y],+1);
	}

	for (int x : ups) upd(x);
	ups.clear();

	return IT[1].min == 4 ? IT[1].cnt : 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