Submission #272799

#	Time	Username	Problem	Language	Result	Execution time	Memory
272799		rqi	Seats (IOI18_seats)	C++14	100 / 100	3786 ms	132068 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef pair<ll, int> T;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define ins insert
#define all(x) begin(x), end(x)

const ll INF = 1e18;
T ID = mp(INF, 0);
T comb(T a, T b){
	if(a.f == b.f) return mp(a.f, a.s+b.s);
	return min(a, b);
}


const int SZ = 1048576;
T seg[2*SZ];
ll lazy[2*SZ];



void pull(int ind){
	seg[ind] = comb(seg[2*ind], seg[2*ind+1]);
}

void push(int ind, int L, int R){
	seg[ind].f+=lazy[ind];
	if(L < R){
		for(int i = 0; i < 2; i++){
			lazy[2*ind+i]+=lazy[ind];
		}
	}
	lazy[ind] = 0;
	return;
}

void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1){
	push(ind, L, R);
	if(L > hi || R < lo) return;
	if(lo <= L && R <= hi){
		lazy[ind] = inc;
		push(ind, L, R);
		//cout << "UPD " << ind << " " << L << " " << R << " " << seg[ind].f << " " << seg[ind].s << "\n";
		return;
	}
	int M = (L+R)/2;
	upd(lo, hi, inc, 2*ind, L, M); upd(lo, hi, inc, 2*ind+1, M+1, R);
	pull(ind);
}

T query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1){
	push(ind, L, R);
	if(L > hi || R < lo) return ID;
	if(lo <= L && R <= hi){
		//cout << ind << "\n";
		return seg[ind];
	}
	int M = (L+R)/2;
	return comb(query(lo, hi, 2*ind, L, M), query(lo, hi, 2*ind+1, M+1, R));
}

const int mx = 1000005;
int H, W;
pi pos[mx];
vector<vi> stu;

vpi rec = vpi{mp(0, 0), mp(0, 1), mp(1, 0), mp(1, 1)};
vpi rec2 = vpi{mp(-1, -1), mp(-1, 0), mp(0, -1), mp(0, 0)};

vector<pair<pi, bool>> fig[8]; 
ll val[8];

vector<pair<pi, int>> rot;

bool works(int r, int c, pi dif){
	r = r+dif.f;
	c = c+dif.s;
	if(r < 0 || H-1 < r) return 0;
	if(c < 0 || W-1 < c) return 0;
	return 1;
}

bool mode = 0;
ll csum[mx];
void updSeat(int r, int c, int con, int typ){
	
	bool good = 1;
	int lo = 0;
	int hi = H*W-1;
	for(auto u: fig[con]){
		if(!works(r, c, u.f)){
			good = 0;
			//cout << "NO WORK " << r << " " << c << " " << con << "\n";
			break;
		}
		if(u.s == 1){
			lo = max(lo, stu[r+u.f.f][c+u.f.s]);
		}
		else{
			hi = min(hi, stu[r+u.f.f][c+u.f.s]-1);
		}
	}
	if(lo > hi) good = 0;
	if(!good) return;
	// cout << "updSeat: " << r << " " << c << " " << con << " " << typ << "\n";
	// cout << "seg update " << lo << " " << hi << " " << val[con]*typ << "\n";
	if(mode == 0){
		csum[lo]+=val[con]*typ;
		csum[hi+1]-=val[con]*typ;
	}
	else upd(lo, hi, val[con]*typ);
}

void give_initial_chart(int _H, int _W, vi R, vi C) {
	
	for(int i = 0; i < 5; i++){
		for(int k = 0; k < 4; k++){
			bool x = 1;
			if(i == k) x = 0;
			fig[i].pb(mp(rec[k], x));
		}
	}
	for(int i = 5; i < 8; i++){
		fig[i].pb(mp(mp(0, 0), 1));
	}
	fig[6].pb(mp(mp(0, 1), 1));
	fig[7].pb(mp(mp(1, 0), 1)); 
	val[0] = val[1] = val[2] = val[3] = 1000000000LL;
	val[4] = 1;
	val[5] = 1;
	val[6] = -1;
	val[7] = -1;

	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 5; j++){
			rot.pb(mp(rec2[i], j));
		}
	}

	for(int i = 5; i < 8; i++){
		rot.pb(mp(mp(0, 0), i));
	}
	rot.pb(mp(rec2[2], 6));
	rot.pb(mp(rec2[1], 7));

	// cout << "rot:\n";
	// for(auto u: rot){
	// 	cout << u.f.f << " " << u.f.s << " " << u.s << "\n";
	// }
	// cout << "\n";

	// for(int i = 0; i < 4; i++){
	// 	int r = rec1[i].f;
	// 	int c = rec1[i].s;
	// 	for(int j = 0; j < 4; j++){
	// 		for(int k = 0; k < 4; k++){
	// 			bool x = 1;
	// 			if(j == k) x = 0;
	// 			fig[4*i+j].pb(mp(mp(r+rec2[k].f, c+rec2[k].s), x));
	// 		}
	// 		val[4*i+j] = 1000000000LL;
	// 	}
	// }

	// for(int i = 0; i < 4; i++){
	// 	int r = rec1[i].f;
	// 	int c = rec1[i].s;
	// 	for(int k = 0; k < 4; k++){
	// 		fig[16+i].pb(mp(mp(r+rec2[k].f, c+rec2[k].s), 1));
	// 	}
	// 	val[16+i] = 1;
	// }
	// for(int i = 0; i <= 4; i++){
	// 	fig[20+i].pb(mp(mp(0, 0), 1));
	// }
	// fig[21].pb(mp(mp(0, -1), 1));
	// fig[22].pb(mp(mp(0, 1), 1));
	// fig[23].pb(mp(mp(-1, 0), 1));
	// fig[24].pb(mp(mp(1, 0), 1));
	// val[20] = 1;
	// val[21] = val[22] = val[23] = val[24] = -1;

	for(int i = SZ; i < 2*SZ; i++){
		seg[i] = mp(0, 1);
	}
	

	// cout << seg[1+SZ].f << " " << seg[1+SZ].s << "\n";
	// T q1 = query(1, 1);
	// cout << q1.f << " " << q1.s << "\n";
	// upd(1, 1, 5);
	// q1 = query(1, 1);
	// cout << q1.f << " " << q1.s << "\n";
	// cout << "////////////////\n";

	H = _H;
	W = _W;
	stu = vector<vi>(H, vi(W, 0));
	for(int i = 0; i < H*W; i++){
		pos[i] = mp(R[i], C[i]);
		stu[R[i]][C[i]] = i;
	}
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			for(int k = 0; k < 8; k++){
				updSeat(i, j, k, 1);
			}
		}
	}

	for(int i = 1; i < H*W; i++){
		csum[i]+=csum[i-1];
		
	}

	for(int i = 0; i < H*W; i++){
		seg[i+SZ] = mp(csum[i], 1);
	}

	for(int i = SZ-1; i >= 1; i--){
		pull(i);
	}

	mode = 1;


	// for(int i = 0; i < H*W; i++){
	// 	T q1 = query(i, i);
	// 	cout << "query " << i << " " << q1.f << " " << q1.s << "\n";;
	// }
	// T q1 = query(0, H*W-1);
	// cout << "query " << " " << q1.f << " " << q1.s << "\n";
}

int swap_seats(int a, int b) {
	//cout << "swap_seats " << a << " " << b << "\n";
	pi pos1 = pos[a];
	pi pos2 = pos[b];
	vector<pair<pi, int>> upds;

	for(auto u: rot){
		upds.pb(mp(mp(pos1.f+u.f.f, pos1.s+u.f.s), u.s));
	}
	for(auto u: rot){
		upds.pb(mp(mp(pos2.f+u.f.f, pos2.s+u.f.s), u.s));
	}

	// for(auto u: upds){
	// 	cout << "upds " << u.f.f << " " << u.f.s << " " << u.s << " " << "\n";
	// }
	sort(all(upds));
	upds.erase(unique(all(upds)), end(upds));

	for(auto u: upds){
		updSeat(u.f.f, u.f.s, u.s, -1);
	}

	
	swap(pos[a], pos[b]);
	swap(stu[pos1.f][pos1.s], stu[pos2.f][pos2.s]);

	for(auto u: upds){
		updSeat(u.f.f, u.f.s, u.s, 1);
	}

	// for(int i = 0; i < H*W; i++){
	// 	T q1 = query(i, i);
	// 	cout << "query " << i << " " << q1.f << " " << q1.s << "\n";;
	// }

	T q = query(0, H*W-1);
	assert(q.f == 1);
 	return q.s;
}

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