Submission #170277

#	Time	Username	Problem	Language	Result	Execution time	Memory
170277		socho	Seats (IOI18_seats)	C++14	11 / 100	4045 ms	228856 KiB

seats

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

struct node_co {
	
	int seg_st, seg_en, seg_mid;
	int valmax, valmin;
	node_co *left, *right;
	
	node_co(int st, int en) {
		seg_st = st;
		seg_en = en;
		int mi = (st + en) / 2;
		seg_mid = mi;
		valmax = valmin = 0;
		if (st == en) return;
		left = new node_co(st, mi);
		right = new node_co(mi+1, en);
	}
	
	void update(int pos, int to) {
		if (pos > seg_en || pos < seg_st) {
			return;
		}
		if (seg_st == seg_en) {
			valmax = to;
			valmin = to;
			return;
		}
		left->update(pos, to);
		right->update(pos, to);
		valmax = max(left->valmax, right->valmax);
		valmin = min(left->valmin, right->valmin);
	}
	
	pair<int, int> query(int a, int b) {
		if (a > seg_en || b < seg_st) return make_pair(INT_MIN, INT_MAX);
		if (a <= seg_st && b >= seg_en) {
			return make_pair(valmax, valmin);
		}
		pair<int, int> le = left->query(a, b);
		pair<int, int> ri = right->query(a, b);
		return make_pair(max(le.first, ri.first), min(le.second, ri.second));
	}
	
} *hno, *vno;

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

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

void valid(int c) {
	pair<int, int> h = hno->query(0, c);
	pair<int, int> v = vno->query(0, c);
	int hdif = h.first - h.second + 1;
	int vdif = v.first - v.second + 1;
	bool ans = false;
	if (c + 1 == (hdif * vdif)) {
		ans = true;
	}
	// cout << " > " << c << ' ' << ans << ' ' << h.first << ' ' << h.second << ' ' << v.first << ' ' << v.second << endl;
	if (ans == work[c]) return;
	if (ans) counter++;
	else counter--;
	work[c] = ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	
	h = H;
	w = W;
	n = (h * w);
	
	hno = new node_co(0, n-1);
	vno = new node_co(0, n-1);
	
	for (int i=0; i<n; i++) {
		hat[i] = R[i];
		vat[i] = C[i];
		// cout << i << ' ' << R[i] << ' ' << C[i] << endl;
		hno->update(i, R[i]);
		vno->update(i, C[i]);
	}
	
	memset(work, 0, sizeof work);
	counter = 0;
	for (int i=0; i<n; i++) {
		valid(i);
	}
	
}

int swap_seats(int a, int b) {
	int ax = hat[a], ay = vat[a];
	int bx = hat[b], by = vat[b];
	hat[b] = ax, vat[b] = ay;
	hat[a] = bx, vat[a] = by;
	hno->update(a, hat[a]);
	hno->update(b, hat[b]);
	vno->update(a, vat[a]);
	vno->update(b, vat[b]);
	for (int i=min(a, b); i<=max(a, b); i++) {
		valid(i);
	}
	return counter;
}

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