Submission #755324

#	Time	Username	Problem	Language	Result	Execution time	Memory
755324		Tekor	Seats (IOI18_seats)	C++17	100 / 100	1435 ms	194124 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ll long long
#define pll pair <ll,ll>
#define all(v) v.begin(),v.end()
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 1e6 + 10;
int n,m,k;
pii c[N];
int cnt[N * 4];
pii t[N * 4],t1[N * 4];
void merge(int v) {
	t[v] = min(t[v + v],t[v + v + 1]);
	cnt[v] = 0;
	if(t[v + v] == t[v])cnt[v] += cnt[v + v];
	if(t[v + v + 1] == t[v])cnt[v] += cnt[v + v + 1];
}
void push(int v) {
	if(t1[v].f) {
		t[v + v].f += t1[v].f;
		t[v + v + 1].f += t1[v].f;
		t1[v + v].f += t1[v].f;
		t1[v + v + 1].f += t1[v].f;	
		t1[v].f = 0;
	}
	if(t1[v].s) {
		t[v + v].s += t1[v].s;
		t[v + v + 1].s += t1[v].s;
		t1[v + v].s += t1[v].s;
		t1[v + v + 1].s += t1[v].s;
		t1[v].s = 0;	
	}
}
void upd(int v,int tl,int tr,int l,int r,int x,bool typ) {
	if(tl > r || tr < l)return;
	if(tl >= l && tr <= r) {
		if(!typ) {
			t[v].f += x;
			t1[v].f += x;
		}else {
			t[v].s += x;
			t1[v].s += x;
		}
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v + v,tl,tm,l,r,x,typ);
	upd(v + v + 1,tm + 1,tr,l,r,x,typ);
	merge(v);
}
void out(int v,int tl,int tr) {
	cout << tl << " " << tr << " with " << t[v].f << " " << t[v].s << " and " << cnt[v] << endl;
	if(tl == tr)return;
	push(v);
	int tm = (tl + tr) / 2;
	out(v + v,tl,tm);
	out(v + v + 1,tm + 1,tr);
}
vector <vector <int> > num,was1;
int tim;
int dob[N],dob1[N],L,R;
void change(int x,int y,int delt,int typ = -1) {
	if(was1[x][y] == tim)return;
	was1[x][y] = tim;
	int mn = k + 10,mn1 = k + 10,mx = -1,mx1 = -1;
	for(int i = x;i <= x + 1;i++) {
		for(int j = y;j <= y + 1;j++) {
			if(i <= 0 || i > n || j <= 0 || j > m) {
				mx1 = mx;
				mx = k + 1;
				if(k + 1 < mn) {
					mn1 = mn;
					mn = k + 1;
				}else {
					mn1 = min(mn1,k + 1);
				}
				continue;
			}
			if(num[i][j] < mn) {
				mn1 = mn;
				mn = num[i][j];
			}else {
				mn1 = min(mn1,num[i][j]);
			}
			if(num[i][j] > mx) {
				mx1 = mx;
				mx = num[i][j];
			}else {
				mx1 = max(mx1,num[i][j]);
			}
		}
	}
	if(typ == 1) {
		dob[mn] += delt;
		dob[mn1] -= delt;
		dob1[mx1] += delt;
		dob1[mx] -= delt;
		return;
	}
	if(mn1 - 1 >= L && mn <= R)upd(1,0,k,max(mn,L),min(mn1 - 1,R),delt,1);
	if(mx - 1 >= L && mx1 <= R)upd(1,0,k,max(mx1,L),min(mx - 1,R),delt,0);
}
void add(int x,int typ = -1) {
	for(int i = -1;i <= 0;i++) {
		for(int j = -1;j <= 0;j++) {
			change(c[x].f + i,c[x].s + j,1,typ);
		}
	}
}
void del(int x) {
	for(int i = -1;i <= 0;i++) {
		for(int j = -1;j <= 0;j++) {
			change(c[x].f + i,c[x].s + j,-1,-1);
		}
	}
}
pii d[N];
void build(int v,int tl,int tr) {
	if(tl == tr) {
		t[v] = d[tl];
		cnt[v] = 1;
		return;
	}	
	int tm = (tl + tr) / 2;
	build(v + v,tl,tm);
	build(v + v + 1,tm + 1,tr);
	merge(v);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n = H;
	m = W;
	vector <int> empt;
	empt.assign(m + 1,0);
	num.assign(n + 1,empt);
	was1 = num;
	k = n * m - 1;
	for(int i = 0;i <= k;i++) {
		c[i] = mp(R[i] + 1,C[i] + 1);
		num[c[i].f][c[i].s] = i;
	}
//	cout << "well" << endl;
	++tim;
	for(int i = 0;i <= k;i++) {
//		cout << i << endl;
		add(i,1);
	}
	int tek = 0,tek1 = 0;
	for(int i = 0;i <= k;i++) {
		tek += dob[i];
		tek1 += dob1[i];
		d[i] = mp(tek1,tek);
	}
	build(1,0,k);
//	out(1,0,k);
}
int swap_seats(int a, int b) {
	if(a > b)swap(a,b);
	L = a;
	R = b;
	++tim;
	del(a);
	del(b);
	swap(c[a],c[b]);
	num[c[a].f][c[a].s] = a;
	num[c[b].f][c[b].s] = b;
	++tim;
	add(a);
	add(b);
//	out(1,0,k);
	return cnt[1];
}

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