Submission #772686

#	Time	Username	Problem	Language	Result	Execution time	Memory
772686		amunduzbaev	Seats (IOI18_seats)	C++17	100 / 100	1468 ms	115336 KiB

seats

#include "seats.h"

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

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll

const int N = 1e6 + 5;

struct ST{
	int tree[N << 2], cnt[N << 2], f[N << 2], a[N];
	
	void build(int l, int r, int x){
		if(l == r) { tree[x] = 0, cnt[x] = 1; return; }
		int m = (l + r) >> 1;
		build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
		cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
	}
	
	ST(){
		build(0, N, 1);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x << 1] += f[x], f[x << 1] += f[x];
		tree[x << 1 | 1] += f[x], f[x << 1 | 1] += f[x];
		f[x] = 0;
	}
	
	void rec(int x){
		tree[x] = tree[x << 1], cnt[x] = cnt[x << 1];
		if(tree[x << 1] > tree[x << 1 | 1]){
			tree[x] = tree[x << 1 | 1], cnt[x] = cnt[x << 1 | 1];
		} else if(tree[x << 1] == tree[x << 1 | 1]){
			cnt[x] += cnt[x << 1 | 1];
		}
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l){
			return;
		}
		if(lx >= l && rx <= r){
			tree[x] += v, f[x] += v;
			return;
		}
		
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		
		rec(x);
	}
	
	void set(int i, int v){
		add(i, N, -a[i] + v, 0, N, 1);
		a[i] = v;
	}
	
	ar<int, 2> get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return {N, N};
		if(lx >= l && rx <= r) return {tree[x], cnt[x]};
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		auto L = get(l, r, lx, m, x << 1);
		auto R = get(l, r, m + 1, rx, x << 1 | 1);
		if(L > R) swap(L, R);
		if(L[0] == R[0]) L[1] += R[1];
		return L;
	}
	
	ar<int, 2> get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree;

int n, m, sz;
vector<int> x, y;
vector<vector<int>> a;

int get(int i, int j, int v){
	int mask = 0;
	if(a[i][j] <= v) mask |= 1;
	if(a[i][j + 1] <= v) mask |= 2;
	if(a[i + 1][j] <= v) mask |= 4;
	if(a[i + 1][j + 1] <= v) mask |= 8;
	return mask;
}

int trans(int old, int nw){
	if(old == 0){
		return 1;
	} else if(__builtin_popcount(old) == 1){
		if(nw == 6 || nw == 9) return 0;
		else return -1;
	} else if(__builtin_popcount(old) == 2){
		if(old == 6 || old == 9) return 0;
		else return 1;
	} else {
		return -1;
	}
}

void rec(int i, int j){
	tree.set(a[i][j], trans(get(i - 1, j - 1, a[i][j] - 1), get(i - 1, j - 1, a[i][j])) + 
					  trans(get(i, j - 1, a[i][j] - 1), get(i, j - 1, a[i][j])) + 
					  trans(get(i - 1, j, a[i][j] - 1), get(i - 1, j, a[i][j])) + 
					  trans(get(i, j, a[i][j] - 1), get(i, j, a[i][j])));
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
	n = h, m = w;
	sz = n * m;
	swap(x, r);
	swap(y, c);
	a.resize(n + 2, vector<int>(m + 2, N));
	
	for(int i=0;i<sz;i++){
		x[i]++, y[i]++;
		a[x[i]][y[i]] = i;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			rec(i, j);
		}
	}
	
	auto ans = tree.get(0, sz - 1);
	assert(ans[0] == 4);
}

int swap_seats(int i, int j){
	swap(x[i], x[j]), swap(y[i], y[j]);
	a[x[i]][y[i]] = i, a[x[j]][y[j]] = j;
	
	auto check = [&](int x, int y){
		return (1 <= x && x <= n && 1 <= y && y <= m);
	};
	
	for(int x_ = x[i] - 1; x_ <= x[i] + 1; x_++){
		for(int y_ = y[i] - 1; y_ <= y[i] + 1; y_++){
			if(check(x_, y_)){
				rec(x_, y_);
			}
		}
	}
	for(int x_ = x[j] - 1; x_ <= x[j] + 1; x_++){
		for(int y_ = y[j] - 1; y_ <= y[j] + 1; y_++){
			if(check(x_, y_)){
				rec(x_, y_);
			}
		}
	}
	
	auto ans = tree.get(0, sz - 1);
	assert(ans[0] == 4);
	return ans[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