Submission #121274

#	Time	Username	Problem	Language	Result	Execution time	Memory
121274		SirCeness	Seats (IOI18_seats)	C++17	11 / 100	4102 ms	253560 KiB

seats

#include <bits/stdc++.h>

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

map<pair<int, int>, int> mapp;
int tmp[4];
int MX;
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] = mapp[mp(i, j)];
	tmp[1] = mapp[mp(i+1, j)];
	tmp[2] = mapp[mp(i, j+1)];
	tmp[3] = mapp[mp(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] = mapp[mp(i, j)];
	tmp[1] = mapp[mp(i+1, j)];
	tmp[2] = mapp[mp(i, j+1)];
	tmp[3] = mapp[mp(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 H, int W, vector<int> RR, vector<int> CC) {
	R = RR;
	C = CC;
	MX = H*W;
	for (int i = 0; i < H*W; i++){
		mapp[mp(R[i], C[i])] = i;
	}
	for (int i = -1; i <= H; i++){
		for (int j = -1; j <= W; j++){
			if (i == -1 || j == -1 || i == H ||j == W) mapp[mp(i, j)] = MX;
		}
	}
	
	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;
	mapp[mp(i1, j1)] = b;
	mapp[mp(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: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30