Submission #138670

#	Time	Username	Problem	Language	Result	Execution time	Memory
138670		Mahdi_Jfri	Seats (IOI18_seats)	C++14	0 / 100	4104 ms	262144 KiB

seats

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;
const int dx[] = {-1 , -1 , 1 , 1 , 0 , 0 , 1 ,-1};
const int dy[] = {-1 ,  1 ,-1 , 1 , 1 ,-1 , 0 , 0};

int n , m , all , x[maxn] , y[maxn];

set<int> stx[maxn] , sty[maxn];

vector<int> pos[maxn] , has[maxn];

int mn[maxn * 4] , cnt[maxn * 4] , Add[maxn * 4];

void build(int s = 0 , int e = all , int v = 1)
{
	cnt[v] = e - s;
	if(e - s < 2)
		return;

	int m = (s + e) / 2;
	build(s , m , 2 * v);
	build(m , e , 2 * v + 1);
}

void add(int l , int r , int val , int s = 0 , int e = all , int v = 1)
{
	while(r != all);
	if(l <= s && e <= r)
	{
		Add[v] += val;
		mn[v] += val;
		return;
	}
	if(r <= s || e <= l)
		return;

	int m = (s + e) / 2;
	add(l , r , val , s , m , 2 * v);
	add(l , r , val , m , e , 2 * v + 1);

	mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
	cnt[v] = 0;

	if(mn[v] == mn[2 * v])
		cnt[v] += cnt[2 * v];
	if(mn[v] == mn[2 * v + 1])
		cnt[v] += cnt[2 * v + 1];

	mn[v] += Add[v];
}

void d(int x , int y , int val)
{
	if(x <= 0 || x > n || y <= 0 || y > m)
		return;
	if(val == -1 && !has[x][y])
		return;
	if(val == 1 && has[x][y])
		return;

	has[x][y] ^= 1;
	val *= -1;
	for(int i = 0; i < 8; i++)
	{
		int nx = x + dx[i] , ny = y + dy[i];
		if(i == 4)
			val *= -1;
		add(pos[x][y] , all , pos[nx][ny] < pos[x][y]? -val : val);
	}
}

void addR(int i)
{
	if(!stx[x[i]].empty())
		add(*stx[x[i]].begin() , all , -2);
	stx[x[i]].insert(i);
	add(*stx[x[i]].begin() , all , 2);
}

void addC(int i)
{
	if(!sty[y[i]].empty())
		add(*sty[y[i]].begin() , all , -2);
	sty[y[i]].insert(i);
	add(*sty[y[i]].begin() , all , 2);
}

void remR(int i)
{
	add(*stx[x[i]].begin() , all , -2);
	stx[x[i]].erase(i);
	if(!stx[x[i]].empty())
		add(*stx[x[i]].begin() , all , 2);
}

void remC(int i)
{
	add(*sty[y[i]].begin() , all , -2);
	sty[y[i]].erase(i);
	if(!sty[y[i]].empty())
		add(*sty[y[i]].begin() , all , 2);
}

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

	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= m + 1; j++)
			pos[i].pb(1e9) , has[i].pb(0);

	for(int i = 0; i < all; i++)
	{
		x[i] = R[i] + 1;
		y[i] = C[i] + 1;

		pos[x[i]][y[i]] = i;
	}

	for(int i = 0; i < all; i++)
	{
		addC(i) , addR(i);
		d(x[i] , y[i] , 1);
	}
}

int swap_seats(int a, int b)
{
	remR(a) , remR(b);
	remC(a) , remC(b);
	d(x[a] , y[a] , -1) , d(x[b] , y[b] , -1);

	for(int i = 0; i < 8; i++)
	{
		d(x[a] + dx[i] , y[a] + dy[i] , -1);
		d(x[b] + dx[i] , y[b] + dy[i] , -1);
	}

	swap(x[a] , x[b]) , swap(y[a] , y[b]);
	swap(pos[x[a]][y[a]] , pos[x[b]][y[b]]);

	addR(a) , addR(b);
	addC(a) , addC(b);
	d(x[a] , y[a] , 1) , d(x[b] , y[b] , 1);

	for(int i = 0; i < 8; i++)
	{
		d(x[a] + dx[i] , y[a] + dy[i] , 1);
		d(x[b] + dx[i] , y[b] + dy[i] , 1);
	}

	return cnt[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