Submission #138743

#	Time	Username	Problem	Language	Result	Execution time	Memory
138743		Mahdi_Jfri	Seats (IOI18_seats)	C++14	44 / 100	4027 ms	58872 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;

int n , a[maxn] , pos[maxn] , cnt[maxn * 4] , mn[maxn * 4] , Add[maxn * 4];

bool has[maxn];

int H , tx[maxn] , ty[maxn];

void build(int s = 0 , int e = n , 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 = n , int v = 1)
{
	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 k , int val)
{
	if(k <= 0 || k > n)
		return;
	if(val == -1 && !has[k])
		return;
	if(val == 1 && has[k])
		return;

	has[k] ^= 1;
	add(pos[k] , n , pos[k - 1] < pos[k]? -1 * val : 1 * val);
	add(pos[k] , n , pos[k + 1] < pos[k]? -1 * val : 1 * val);
}

void give_initial_chart(int HH, int W, vector<int> R, vector<int> C)
{
	H = HH;
	n = H * W;
	build();
	for(int i = 0; i < n; i++)
	{
		tx[i] = R[i] , ty[i] = C[i];
		a[i] = C[i] + 1;
		pos[a[i]] = i;
	}
	pos[0] = pos[n + 1] = 1e9;

	for(int i = 0; i < n; i++)
		d(a[i] , 1);
}

int swap_seats(int x, int y)
{
	if(H == 1)
	{
		for(int i = -1; i <= 1; i++)
			d(a[x] + i , -1) , d(a[y] + i , -1);

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

		for(int i = -1; i <= 1; i++)
			d(a[x] + i , 1) , d(a[y] + i , 1);

		return cnt[1];
	}
	else
	{
		swap(tx[x] , tx[y]);
		swap(ty[x] , ty[y]);

		int res = 0 , mnx = 1e9 , mny = 1e9 , mxx = -1 , mxy = -1;
		for(int i = 0; i < n; i++)
		{
			mnx = min(mnx , tx[i]);
			mny = min(mny , ty[i]);

			mxx = max(mxx , tx[i]);
			mxy = max(mxy , ty[i]);

			if((mxx - mnx + 1) * (mxy - mny + 1) == i + 1)
				res++;
		}

		return res;
	}
}

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