Submission #528635

#	Time	Username	Problem	Language	Result	Execution time	Memory
528635		lovro_nidogon1	Seats (IOI18_seats)	C++14	100 / 100	1482 ms	115044 KiB

seats

#include<bits/stdc++.h>
#define breturn return
#define f first
#define s second
using namespace std;
int h, w, lol, xd, q, arr[1100101], n, bn, sus;
int dx[] = {-1, -1, 0, 0};
int dy[] = {0, -1, -1, 0};
pair<int, int> tour[2201000];
int laz[2200100];
vector<vector<int> > mat;
vector<int> r, c, cum, ab, bb;
pair<pair<int, int>, pair<int, int> > get_interval(int x, int y) {
	int val[] = {mat[x][y], mat[x + 1][y], mat[x][y + 1], mat[x + 1][y + 1]};
	sort(val, val + 4);
	breturn {{val[0], val[1]}, {val[2], val[3]}};	
}
void acom(int x) {
	if(tour[x * 2].f == tour[x * 2 + 1].f) tour[x] = {tour[x * 2].f, tour[x * 2].s + tour[x * 2 + 1].s};
	else if(tour[x * 2].f < tour[x * 2 + 1].f) tour[x] = tour[x * 2];
	else tour[x] = tour[x * 2 + 1];
}
void upd(int ax, int bx, int val, int x = 1, int l = 0, int r = bn - 1) {
	if(ax > bx) breturn;
	if(l >= ax and r <= bx) laz[x] += val;		
	tour[x].f += laz[x];
	if(x < bn) laz[x * 2] += laz[x], laz[x * 2 + 1] += laz[x];	
	laz[x] = 0;
	if((l >= ax and r <= bx) or l > bx or r < ax) breturn;
	int mid = (l + r)/2;
	upd(ax, bx, val, x * 2, l, mid);
	upd(ax, bx, val, x * 2 + 1, mid + 1, r);
	acom(x);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  	h = H;
  	w = W;
  	for(int i = 0; i < h * w; i++) c.push_back(C[i] + 1), r.push_back(R[i] + 1);
	n = h * w;
	for(int i = 0; i < w + 2; i++) cum.push_back(h * w);
	for(int i = 0; i < h + 2; i++) mat.push_back(cum);
	for(int i = 0; i < h * w; i++) mat[r[i]][c[i]] = i;
	for(int i = 0; i < h + 1; i++) for(int j = 0; j < w + 1; j++) {
		auto p = get_interval(i, j);
		arr[p.f.f]++;
		arr[p.f.s]--;
		arr[p.s.f]++;
		arr[p.s.s]--; 	
	}
	for(bn = 1; bn < n; bn *= 2);
	for(int i = 0; i < bn; i++) tour[i + bn] = {1e9, 0};
	for(int i = 0; i < n; i++) {
		sus += arr[i];
		tour[i + bn] = {sus, 1};
	}
	for(int i = bn - 1; i; i--) acom(i);
}
int swap_seats(int a, int b) {
	for(int j = 0; j < 4; j++) {
		auto p = get_interval(r[a] + dx[j], c[a] + dy[j]);
		upd(p.f.f, p.f.s - 1, -1);
		upd(p.s.f, p.s.s - 1, -1);
		p = get_interval(r[b] + dx[j], c[b] + dy[j]);
		upd(p.f.f, p.f.s - 1, -1);
		upd(p.s.f, p.s.s - 1, -1);
	}
	swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	for(int j = 0; j < 4; j++) {
		auto p = get_interval(r[a] + dx[j], c[a] + dy[j]);
		upd(p.f.f, p.f.s - 1, 1);
		upd(p.s.f, p.s.s - 1, 1);
		p = get_interval(r[b] + dx[j], c[b] + dy[j]);
		upd(p.f.f, p.f.s - 1, 1);
		upd(p.s.f, p.s.s - 1, 1);
	}
	if(tour[1].f == 4) breturn tour[1].s;
	breturn 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