Submission #528494

#	Time	Username	Problem	Language	Result	Execution time	Memory
528494		lovro_nidogon1	Seats (IOI18_seats)	C++14	0 / 100	368 ms	95932 KiB

seats

#include<bits/stdc++.h>
#define breturn return
#include"seats.h"
#define f first
#define s second
using namespace std;
int h, w, lol, xd, q, arr[1000101], n, bn, sus;
int dx[] = {-1, -1, 0, 0};
int dy[] = {0, -1, -1, 0};
pair<int, int> tour[2001000];
int laz[2001000];
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(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 debug() {
	for(int i = 1; i < 2 * bn; i++) {
		cout << tour[i].f  << "~" << tour[i].s << " ";
		if((1 << (int)log2(i + 1)) == i + 1) cout << '\n';
	}
	for(int i = 1; i < 2 * bn; i++) {
		cout << laz[i] << " ";
		if((1 << (int)log2(i + 1)) == i + 1) cout << '\n';
	}	
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  	h = H;
  	w = W;
  	r = R;
  	c = C;	
	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: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30