Submission #1071767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071767		jcelin	Seats (IOI18_seats)	C++14	0 / 100	1390 ms	76884 KiB

seats

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

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

vi mat[MAXN];
ii pos[MAXN];
int sz;
bool bio[MAXN];

struct tournament{
	ii seg[trsz];
	int p[trsz];
	
	ii merge(ii a, ii b){
		if(a.X != b.X) return min(a, b);
		return {a.X, a.Y + b.Y};
	}
	
	tournament(){
		fill(p, p + trsz, 0);
		for(int i=off; i<trsz; i++) seg[i] = {0, 1};
		for(int i=off-1; i; i--) seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
	}
	
	void prop(int x){
		if(p[x] == 0) return;
		seg[x].X += p[x];
		if(x < off) p[x * 2] += p[x], p[x * 2 + 1] += p[x];
		p[x] = 0;
	}
	
	void update(int x, int lo, int hi, int a, int b, int vl){
		if(a >= b) return;
		prop(x);
		if(lo >= b or hi <= a) return;
		if(lo >= a and hi <= b){
			p[x] = vl;
			prop(x);
			return;
		}
		int mid = (lo + hi) / 2;
		update(x * 2, lo, mid, a, b, vl);
		update(x * 2 + 1, mid, hi, a, b, vl);
		seg[x] = merge(seg[x * 2], seg[x * 2 + 1]);
	}
	
	ii query(int x, int lo, int hi, int a, int b){
		prop(x);
		if(lo >= b or hi <= a) return {inf, 0};
		if(lo >= a and hi <= b) return seg[x];
		int mid = (lo + hi) / 2;
		return merge(query(x * 2, lo, mid, a, b), query(x * 2 + 1, mid, hi, a, b));
	}
	
	int qry(int l, int r){
		ii vl = query(1, 0, off, l, r);
		if(vl.X == 4) return vl.Y;
		return 0;
	}
}t;

int vec[4];
void add(int i, int j, int vl){
	for(int di=0; di<=1; di++){
		for(int dj=0; dj<=1; dj++){
			vec[di * 2 + dj] = mat[i + di][j + dj];
		}
	}
	sort(vec, vec + 4);
	t.update(1, 0, off, vec[0], vec[1], 1 * vl);
	t.update(1, 0, off, vec[2], vec[3], 5 * vl);
}

void give_initial_chart(int r, int s, vi a, vi b){
	sz = r * s;
	for(int i=0; i<r+2; i++) mat[i].resize(s + 2, sz);
	for(int i=0; i<sz; i++){
		mat[a[i] + 1][b[i] + 1] = i;
		pos[i] = {a[i] + 1, b[i] + 1};
	}
	
	for(int i=0; i<=r; i++) for(int j=0; j<=s; j++) add(i, j, 1);
}

ii del[8];
int s;

int swap_seats(int a, int b){
	int r1, s1, r2, s2;
	tie(r1, s1) = pos[a];
	tie(r2, s2) = pos[b];
	
	s = 0;
	for(int i=-1; i<=0; i++){
		for(int j=-1; j<=0; j++){
			if(!bio[mat[r1 + i][s1 + j]]) del[s++] = {r1 + i, s1 + j};
			if(!bio[mat[r2 + i][s2 + j]]) del[s++] = {r2 + i, s2 + j};
			bio[mat[r1 + i][s1 + j]] = 1;
			bio[mat[r2 + i][s2 + j]] = 1;
		}
	}
	
	for(int i=0; i<s; i++){
		add(del[i].X, del[i].Y, -1);
		bio[mat[del[i].X][del[i].Y]] = 0;	
	}
	
	swap(pos[a], pos[b]);
	swap(mat[r1][s1], mat[r2][s2]);
	for(int i=0; i<s; i++) add(del[i].X, del[i].Y, 1);
	
	return t.qry(0, sz);
}

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