Submission #419239

#	Time	Username	Problem	Language	Result	Execution time	Memory
419239		peuch	Seats (IOI18_seats)	C++17	31 / 100	4069 ms	101272 KiB

seats

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

const int MAXN = 1e6 + 10;
const int MAXW = 1e3 + 10;

struct node{
	int minx, maxx, miny, maxy;
	node(int _minx = MAXN, int _maxx = -1, int _miny = MAXN, int _maxy = -1){
		minx = _minx;
		maxx = _maxx;
		miny = _miny;
		maxy = _maxy;
	}
	node operator + (node a){
		node ret;
		ret.minx = min(minx, a.minx);
		ret.maxx = max(maxx, a.maxx);
		ret.miny = min(miny, a.miny);
		ret.maxy = max(maxy, a.maxy);
		return ret;
	}
	void print(){
		printf("%d %d %d %d\n", minx, maxx, miny, maxy);
	}
};

vector<int> r, c;
int h, w;

node seg[4 * MAXN];
int seg2[4 * MAXN], lz[4 * MAXN];

void build(int pos, int ini, int fim);
void update(int pos, int ini, int fim, int id, node val);
node query(int pos, int ini, int fim, int p, int q);
void refresh(int pos, int ini, int fim);
void update2(int pos, int ini, int fim, int p, int q, int val);

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	r = R, c = C;
	h = H, w = W;
	build(1, 0, h * w - 1);
	for(int i = 0; i < h * w; ){
		node val = query(1, 0, h*w-1, 0, i);
		int mn_x = val.minx, mx_x = val.maxx, mn_y = val.miny, mx_y = val.maxy;
		if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1)
			update2(1, 0, h * w - 1, i, i, 1);
		i = max(i+1, (mx_x-mn_x+1)*(mx_y-mn_y+1)-1);
	}
}

int swap_seats(int a, int b) {
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	update(1, 0, h * w - 1, a, node(r[a], r[a], c[a], c[a]));
	update(1, 0, h * w - 1, b, node(r[b], r[b], c[b], c[b]));
	if(a > b) swap(a, b);
	update2(1, 0, h * w - 1, a, b, -1);
	for(int i = a; i <= b; ){
		node val = query(1, 0, h*w-1, 0, i);
		int mn_x = val.minx, mx_x = val.maxx, mn_y = val.miny, mx_y = val.maxy;
		if ((mx_x-mn_x+1)*(mx_y-mn_y+1) == i+1)
			update2(1, 0, h * w - 1, i, i, 1);
 
		i = max(i+1, (mx_x-mn_x+1)*(mx_y-mn_y+1)-1);
	}
	return seg2[1];
}

void build(int pos, int ini, int fim){
	if(ini == fim){
		seg[pos] = node(r[ini], r[ini], c[ini], c[ini]);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	build(e, ini, mid);
	build(d, mid + 1, fim);
	seg[pos] = seg[e] + seg[d];
}

void update(int pos, int ini, int fim, int id, node val){
	if(ini > id || fim < id) return;
	if(ini == fim){
		seg[pos] = val;
		return;
	}
	int mid = (ini + fim) >> 1, e = 2 * pos, d = e + 1;
	if(id <= mid) update(e, ini, mid, id, val);
	else update(d, mid + 1, fim, id, val);
	seg[pos] = seg[e] + seg[d];
}

node query(int pos, int ini, int fim, int p, int q){
	if(ini > q || fim < p) return node();
	if(ini >= p && fim <= q) return seg[pos];
	int mid = (ini + fim) >> 1, e = 2 * pos, d = e + 1;
	return query(e, ini, mid, p, q) + query(d, mid + 1, fim, p, q); 
}

void refresh(int pos, int ini, int fim){
	if(lz[pos] == 0) return;
	if(lz[pos] > 0) seg2[pos] = lz[pos];
	else seg2[pos] = 0;
	if(ini != fim){
		int e = 2 * pos, d = e + 1;
		lz[e] = lz[pos];
		lz[d] = lz[pos];
	}
	lz[pos] = 0;
}

void update2(int pos, int ini, int fim, int p, int q, int val){
	refresh(pos, ini, fim);
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		lz[pos] = val;
		refresh(pos, ini, fim);
		return;
	}
	int mid = (ini + fim) >> 1, e = 2 * pos, d = e + 1;
	update2(e, ini, mid, p, q, val);
	update2(d, mid + 1, fim, p, q, val);
	seg2[pos] = seg2[e] + seg2[d];
}

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