Submission #936548

#	Time	Username	Problem	Language	Result	Execution time	Memory
936548		Trisanu_Das	Seats (IOI18_seats)	C++17	50 / 100	4046 ms	99920 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] , is[maxn] , SUM;
 
int mxxt[maxn] , mxyt[maxn] , mnxt[maxn] , mnyt[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 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)
			SUM++ , is[i] = 1;
 
		mxxt[i] = mxx , mnxt[i] = mnx;
		mxyt[i] = mxy , mnyt[i] = mny;
	}
}
 
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 mnx = 1e9 , mny = 1e9 , mxx = -1 , mxy = -1;
		int k = min(x , y);
		if(k)
			mnx = mnxt[k - 1] , mxx = mxxt[k - 1] , mny = mnyt[k - 1] , mxy = mxyt[k - 1];
		for(int i = min(x , y); i <= max(x , y); i++)
		{
			SUM -= is[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)
				SUM++ , is[i] = 1;
			else
				is[i] = 0;
 
			mxxt[i] = mxx , mnxt[i] = mnx;
			mxyt[i] = mxy , mnyt[i] = mny;
		}
 
		return SUM;
	}
}

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