Submission #292545

#	Time	Username	Problem	Language	Result	Execution time	Memory
292545		oolimry	Seats (IOI18_seats)	C++14	11 / 100	4097 ms	129940 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

const int ruin = 10; ///anything >= 4

vector<vector<int> > arr;
ii pos[1000005];

int rows, cols;
int n;

inline ii merge(ii a, ii b){
	if(a.first == b.first) return ii(a.first, a.second+b.second);
	else return min(a, b);
}

struct node{
	int s, e, m;
	ii val; int lazy;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = ii(0,e-s+1), lazy = 0;
		if(s != e) l = new node(s, m), r = new node(m+1, e);
	}
	
	void apply(int L){
		lazy += L;
		val.first += L;
	}
	
	void push(){
		if(s != e && lazy != 0){
			l->apply(lazy);
			r->apply(lazy);
			lazy = 0;
		}
	}
	
	void update(int S, int E, int L){
		if(S > E) return;
		push();
		if(S == s && e == E){
			apply(L);
			return;
		}
		if(E <= m) l->update(S, E, L);
		else if(S >= m+1) r->update(S, E, L);
		else{
			l->update(S, m, L);
			r->update(m+1, E, L);
		}
		val = merge(l->val, r->val);
	}
	
	int query(){
		push();
		return val.second;
	}
	
	void out(){
		push();
		//cout << s << " " << e << ": " << val.first << "\n";
		if(s != e){
			l->out();
			r->out();
		}
	}
} *root;

inline void update(int R, int C, bool undo){
	vector<int> v = {arr[R][C], arr[R][C+1], arr[R+1][C], arr[R+1][C+1]};
	sort(all(v));
	int a = v[0], b = v[1], c = v[2], d = v[3];
	
	//cout << a << " " << b << " " << c << " " << d << endl;
	
	if(undo){
		root->update(a, b-1, -1);
		root->update(c, d-1, -ruin);
	}
	else{
		root->update(a, b-1, 1);
		root->update(c, d-1, ruin);
	}
}

inline void square(ii x, bool undo){
	int r = x.first, c = x.second;
	update(r, c, undo);
	update(r-1, c, undo);
	update(r, c-1, undo);
	update(r-1, c-1, undo);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	rows = H, cols = W, n = rows*cols;
	
	arr.resize(rows+2);
	for(int i = 0;i <= rows+1;i++){
		arr[i].assign(cols+2, n);
	}
	
	for(int i = 0;i < rows*cols;i++){
		int r = R[i]+1, c = C[i]+1;
		arr[r][c] = i;
		pos[i] = ii(r,c);
	}
	
	root = new node(0, n-1);
	
	for(int r = 0;r <= rows;r++){
		for(int c = 0;c <= cols;c++){
			update(r, c, false);
		}
	}
	
	//cout << root->query() << '\n';
	root->out();
}



int swap_seats(int a, int b){
	ii A = pos[a], B = pos[b];
	
	square(A, true); square(B, true);
	
	swap(pos[a], pos[b]);
	arr[A.first][A.second] = b;
	arr[B.first][B.second] = a;
	
	square(A, false); square(B, false);
	
	return root->query();
}

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