Submission #139340

#	Time	Username	Problem	Language	Result	Execution time	Memory
139340		super_j6	Seats (IOI18_seats)	C++14	100 / 100	3420 ms	204668 KiB

seats

#include "seats.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
 
struct sq{
	int t1 = 0, t3 = 0;
	
	friend bool operator<(sq a, sq b){
		return make_pair(a.t1 , a.t3) < make_pair(b.t1, b.t3);
	}
	
	friend bool operator==(sq a, sq b){
		return make_pair(a.t1 , a.t3) == make_pair(b.t1, b.t3);
	}
	
	friend sq operator+(sq a, sq b){
		return (sq){a.t1 + b.t1, a.t3 + b.t3};
	}
	
	friend sq operator*(int a, sq b){
		return (sq){a * b.t1, a * b.t3};
	}
};
 
struct segTree{
	int l, r;
	segTree *left, *right;
	pair<sq, int> val;
	sq lazy;
	
	segTree(int a, int b){
		l = a;
		r = b;
		
		if(l != r){
			int mid = (l + r) / 2;
			left = new segTree(l, mid);
			right = new segTree(mid + 1, r);
			val.second = left->val.second + right->val.second;
		}else{
			val.second = 1;
		}
	}
	
	void add(int a, int b, sq x){
		if(l > b || r < a) return;
		if(l >= a && r <= b){
			val.first = val.first + x + lazy;
			if(l != r){
				left->lazy = left->lazy + x + lazy;
				right->lazy = right->lazy + x + lazy;
			}
			lazy = (sq){0, 0};
			return;
		}
		
		left->lazy = left->lazy + lazy;
		right->lazy = right->lazy + lazy;
		lazy = (sq){0, 0};
		
		left->add(a, b, x);
		right->add(a, b, x);
		
		sq lv = left->val.first + left->lazy, rv = right->val.first + right->lazy;
		val.first = min(lv, rv);
		val.second = 0;
		if(val.first == lv) val.second += left->val.second;
		if(val.first == rv) val.second += right->val.second;
 	}
};
 
const int maxn = 1000000;
int h, w, n;
bool used[maxn];
int r[maxn], c[maxn];
vector<vector<int>> p;
segTree *tre;
 
int dx[9] = {0, 1, 1, 0, -1, -1, -1, 0, 1};
int dy[9] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
sq d[5] = {(sq){0, 0}, (sq){1, 0}, (sq){-1, 0}, (sq){0, 1}, (sq){0, -1}};
 
sq tch(int x, int y, int v){
	int ret = 0;
	for(int i = 0; i < 4; i++){
		ret += (p[x + dx[i]][y + dy[i]] <= v);
	}
	return d[ret];
}
 
void chg(int v, int m){
	sq s;
	for(int i = 0; i < 4; i++){
		s = s + tch(r[v] - dx[i], c[v] - dy[i], v);
	}
	tre->add(v, n - 1, m * s);
}
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
	h = H + 2, w = W + 2, n = H * W;
	p.resize(h);
	for(int i = 0; i < h; i++) p[i].resize(w);
	tre = new segTree(0, n - 1);
	
	for(int i = 0; i < n; i++){
		r[i] = R[i] + 1;
		c[i] = C[i] + 1;
		p[r[i]][c[i]] = i;
	}
	for(int i = 0; i < h; i++) p[i][0] = p[i][w - 1] = maxn;
	for(int i = 0; i < w; i++) p[0][i] = p[h - 1][i] = maxn;
	
	for(int i = 0; i < n; i++) chg(i, 1);
}
 
void swp(int v, int m){
	for(int i = 0; i < 9; i++){
		int nv = p[r[v] + dx[i]][c[v] + dy[i]];
		if(nv != maxn && !used[nv]){
			chg(nv, m);
			used[nv] = 1;
		}
	}
}
 
void rst(int v){
	for(int i = 0; i < 9; i++){
		int nv = p[r[v] + dx[i]][c[v] + dy[i]];
		if(nv != maxn) used[nv] = 0;
	}
}
 
int swap_seats(int a, int b){
	swp(a, -1), swp(b, -1);
	rst(a), rst(b);
	
	swap(c[a], c[b]);
	swap(r[a], r[b]);
	swap(p[r[a]][c[a]], p[r[b]][c[b]]);
	
	swp(a, 1), swp(b, 1);
	rst(a), rst(b);
	/*
	for(int i = 1; i < h - 1; i++){
		for(int j = 1; j < w - 1; j++) cout << p[i][j] << " ";
		cout << endl;
	}
	*/
	return tre->val.second;
}
 
/*
int main(){
	int h, w;
	cin >> h >> w;
	
	vector<int> a(h * w), b(h * w);
	for(int i = 0; i < h * w; i++) cin >> a[i] >> b[i];
	
	give_initial_chart(h, w, a, b);
	cout << swap_seats(0, 5) << endl;
	cout << swap_seats(0, 5) << endl;
	
	return 0;
}
*/

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