Submission #121287

#	Time	Username	Problem	Language	Result	Execution time	Memory
121287		SirCeness	Seats (IOI18_seats)	C++17	100 / 100	3587 ms	119292 KiB

seats

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inf 1000000009
using namespace std;
typedef long long ll;

vector<vector<int> > mat;
int tmp[4];
int MX;
int H, W;
vector<int> R;
vector<int> C;
int lazy[4000006];
int minn[4000006];
int countt[4000006];

void stc(int node, int l, int r){
	if (l == r){
		minn[node] = 0;
		countt[node] = 1;
		lazy[node] = 0;
	} else {
		int m = (l+r)/2;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		minn[node] = min(minn[node*2], minn[node*2+1]);
		countt[node] = 0;
		if (minn[node] == minn[node*2]) countt[node] += countt[node*2];
		if (minn[node] == minn[node*2+1]) countt[node] += countt[node*2+1];
		lazy[node] = 0;
	}
}

int get(int node){
	return minn[node] + lazy[node];
}

void push(int node){
	minn[node] += lazy[node];
	lazy[node*2+1] += lazy[node];
	lazy[node*2] += lazy[node];
	lazy[node] = 0;
}

void stu(int node, int l, int r, int sl, int sr, int val){
	if (sl <= l && r <= sr){
		lazy[node] += val;
	} else if (r < sl ||sr < l){
		return;
	} else {
		int m = (l+r)/2;
		push(node);
		stu(node*2, l, m, sl, sr, val);
		stu(node*2+1, m+1, r, sl, sr, val);
		
		minn[node] = min(get(node*2), get(node*2+1));
		countt[node] = 0;
		if (minn[node] == get(node*2)) countt[node] += countt[node*2];
		if (minn[node] == get(node*2+1)) countt[node] += countt[node*2+1];
	}
}

void yap(int i, int j){
	tmp[0] = (i == -1 || j == -1) ? MX : mat[i][j];
	tmp[1] = (i+1 == H || j == -1) ? MX : mat[i+1][j];
	tmp[2] = (i == -1 || j+1 == W) ? MX : mat[i][j+1];
	tmp[3] = (i+1 == H || j+1 == W) ? MX : mat[i+1][j+1];
	sort(tmp, tmp+4);
	//cout << "yap: " << tmp[0] << ", " << tmp[1] << ", " << tmp[2] << ", " << tmp[3] << endl;
	if (tmp[0] < tmp[1]) stu(1, 0, MX-1, tmp[0], tmp[1]-1, +1);
	if (tmp[2] < tmp[3]) stu(1, 0, MX-1, tmp[2], tmp[3]-1, +1);
	//if (tmp[0] < tmp[1]) cout << tmp[0] << " - " << tmp[1]-1 << ": +1" << endl;
	//if (tmp[2] < tmp[3]) cout << tmp[2] << " - " << tmp[3]-1 << ": +1" << endl;
}

void boz(int i, int j){
	tmp[0] = (i == -1 || j == -1) ? MX : mat[i][j];
	tmp[1] = (i+1 == H || j == -1) ? MX : mat[i+1][j];
	tmp[2] = (i == -1 || j+1 == W) ? MX : mat[i][j+1];
	tmp[3] = (i+1 == H || j+1 == W) ? MX : mat[i+1][j+1];
	sort(tmp, tmp+4);
	if (tmp[0] != -1) stu(1, 0, MX-1, tmp[0], tmp[1]-1, -1);
	if (tmp[2] != -1) stu(1, 0, MX-1, tmp[2], tmp[3]-1, -1);
}

int getnode(int node, int l, int r, int ind){
	if (l == r) return get(node);
	else {
		int m = (l+r)/2;
		push(node);
		if (ind <= m) return getnode(node*2, l, m, ind);
		else return getnode(node*2+1, m+1, r, ind);
	}
}

void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {
	H = HH;
	W = WW;
	R = RR;
	C = CC;
	MX = H*W;
	mat.resize(H);
	for (int i = 0; i < H; i++) mat[i].resize(W);
	for (int i = 0; i < MX; i++){
		mat[R[i]][C[i]] = i;
	}
	
	/*for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			cout << mat[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/
	
	stc(1, 0, MX-1);
	
	for (int i = -1; i < H; i++){
		for (int j = -1; j < W; j++){
			yap(i, j);
		}
	}
	
	/*for (int i = 0; i < MX; i++) cout << getnode(1, 0, MX-1, i) << " ";
	cout << endl;*/
	
}

int swap_seats(int a, int b) {
	int i1 = R[a];
	int j1 = C[a];
	int i2 = R[b];
	int j2 = C[b];
	boz(i1-1, j1-1);
	boz(i1-1, j1);
	boz(i1, j1-1);
	boz(i1, j1);
	boz(i2-1, j2-1);
	boz(i2-1, j2);
	boz(i2, j2-1);
	boz(i2, j2);
	R[a] = i2;
	R[b] = i1;
	C[a] = j2;
	C[b] = j1;
	mat[i1][j1] = b;
	mat[i2][j2] = a;
	yap(i1, j1);
	yap(i1, j1-1);
	yap(i1-1, j1);
	yap(i1-1, j1-1);
	yap(i2, j2);
	yap(i2, j2-1);
	yap(i2-1, j2);
	yap(i2-1, j2-1);
	return countt[1];
}
/*
int main(){
	freopen("stl.gir", "r", stdin);
	
	int h, w;
	cin >> h >> w;
	vector<int> r;
	vector<int> c;
	for (int i = 0; i < h*w; i++){
		int a, b;
		cin >> a >> b;
		r.pb(a);
		c.pb(b);
	}
	give_initial_chart(h, w, r, c);
	int q;
	cin >> q;
	while(q--){
		int a, b;
		cin >> a >> b;
		cout << swap_seats(a, b) << endl;
	}
	
}*/

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