Submission #115555

#	Time	Username	Problem	Language	Result	Execution time	Memory
115555		WhipppedCream	Seats (IOI18_seats)	C++17	5 / 100	4089 ms	72696 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
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 r[maxn], c[maxn];
int n, m;

struct node
{
	int mnr, mxr;
	int mnc, mxc;
	node(){}
	node(int a, int b, int c, int d) : mnr(a), mxr(b), mnc(c), mxc(d) {}
	bool operator == (node other) const
	{
		if(mnr != other.mnr) return false;
		if(mnc != other.mnc) return false;
		if(mxr != other.mxr) return false;
		if(mxc != other.mxc) return false;
		return true;
	}
};

node st[4*maxn];

node pull(node &x, node &y)
{
	return node(min(x.mnr, y.mnr), max(x.mxr, y.mxr), min(x.mnc, y.mnc), max(x.mxc, y.mxc));
}

void update(int x, int dr, int dc, int p = 1, int L = 0, int R = n*m-1)
{
	if(L == R) 
	{
		st[p] = node(dr, dr, dc, dc);
		return;
	}
	int M = (L+R)/2;
	if(x<= M) update(x, dr, dc, 2*p, L, M);
	else update(x, dr, dc, 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 = n*m-1)
{
	if(i> R || j< L) return node(1e9, 0, 1e9, 0);
	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);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	n = H;
	m = W;
	for(int i = 0; i< n*m; i++)
	{
		r[i] = R[i]; c[i] = C[i];
		update(i, r[i], c[i]);
	}
}

int swap_seats(int a, int b)
{
	update(a, r[b], c[b]);
	update(b, r[a], c[a]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	int st = 0;
	int ans = 0;
	while(st< n*m)
	{
		node x = ask(0, st);
		int lo = st, hi = n*m-1;
		while(lo< hi)
		{
			int mid = (lo+hi+1)/2;
			node y = ask(0, mid);
			if(x == y) lo = mid;
			else hi = mid-1;
		}
		int sz = (x.mxr-x.mnr+1)*(x.mxc-x.mnc+1);
		ans += st+1<= sz && sz<= lo+1;
		st = lo+1;
	}
	return ans;
}

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