Submission #170260

#	Time	Username	Problem	Language	Result	Execution time	Memory
170260		socho	Seats (IOI18_seats)	C++14	0 / 100	4042 ms	262144 KiB

seats

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

struct node_max {
	
	int seg_st, seg_en, seg_mid;
	int val;
	node_max *left, *right;
	
	node_max(int st, int en) {
		seg_st = st;
		seg_en = en;
		int mi = (st + en) / 2;
		seg_mid = mi;
		val = 0;
		if (st == en) return;
		left = new node_max(st, mi);
		right = new node_max(mi+1, en);
	}
	
	void update(int pos, int to) {
		if (pos > seg_en || pos < seg_st) {
			return;
		}
		if (seg_st == seg_en) {
			val = to;
			return;
		}
		left->update(pos, to);
		right->update(pos, to);
		val = max(left->val, right->val);
	}
	
	int query(int a, int b) {
		if (a > seg_en) return INT_MIN;
		if (b < seg_st) return INT_MIN;
		if (a <= seg_st && b >= seg_en) {
			return val;
		}
		return max(left->query(a, b), right->query(a, b));
	}
	
} *hmax, *vmax;

struct node_min {
	
	int seg_st, seg_en, seg_mid;
	int val;
	node_min *left, *right;
	
	node_min(int st, int en) {
		seg_st = st;
		seg_en = en;
		int mi = (st + en) / 2;
		seg_mid = mi;
		val = 0;
		if (st == en) return;
		left = new node_min(st, mi);
		right = new node_min(mi+1, en);
	}
	
	void update(int pos, int to) {
		if (pos > seg_en || pos < seg_st) {
			return;
		}
		if (seg_st == seg_en) {
			val = to;
			return;
		}
		left->update(pos, to);
		right->update(pos, to);
		val = min(left->val, right->val);
	}
	
	int query(int a, int b) {
		if (a > seg_en) return INT_MAX;
		if (b < seg_st) return INT_MAX;
		if (a <= seg_st && b >= seg_en) {
			return val;
		}
		return min(left->query(a, b), right->query(a, b));
	}
	
} *hmin, *vmin;

const int MXN = 1000005;
int h, w, n;

int hat[MXN], vat[MXN];
bool work[MXN];
int counter = 0;

void valid(int c) {
	int hmi = hmin->query(0, c);
	int hma = hmax->query(0, c);
	int vmi = vmin->query(0, c);
	int vma = vmax->query(0, c);
	bool ans = (((vma - vmi + 1) * (hma - hmi + 1)) == (c + 1));
	if (ans == work[c]) return;
	if (work[c]) {
		work[c] = ans;
		counter--;
	}
	else {
		work[c] = ans;
		counter++;
	}
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	
	h = H;
	w = W;
	n = (h * w);
	
	// rows
	hmax = new node_max(0, n-1);
	hmin = new node_min(0, n-1);
	// cols
	vmax = new node_max(0, n-1);
	vmin = new node_min(0, n-1);
	
	for (int i=0; i<n; i++) {
		int r = R[i];
		int c = C[i];
		hmax->update(i, r);
		hmin->update(i, r);
		vmax->update(i, c);
		vmin->update(i, c);
		hat[i] = r;
		vat[i] = c;
	}
	
	memset(work, 0, sizeof work);
	for (int i=0; i<n; i++) {
		valid(i);
	}
	
	
}

int swap_seats(int a, int b) {
	int ax = hat[a];
	int ay = vat[a];
	int bx = hat[b];
	int by = vat[b];
	hmax->update(a, bx);
	hmin->update(a, bx);
	vmax->update(a, by);
	vmin->update(a, by);
	hmax->update(b, ax);
	hmin->update(b, ax);
	vmax->update(b, ay);
	vmin->update(b, ay);
	hat[a] = bx;
	vat[a] = by;
	hat[b] = ax;
	vat[b] = ay;
	for (int i=a; i<=b; i++) {
		valid(i);
	}
	return counter;
	
}

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