Submission #596894

#	Time	Username	Problem	Language	Result	Execution time	Memory
596894		Lucpp	Seats (IOI18_seats)	C++17	20 / 100	4070 ms	133812 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

struct MinSeg{
	vector<int> seg;
	int cap;
	void init(vector<int> v){
		for(cap = 1; cap < (int)v.size(); cap *= 2);
		seg.resize(2*cap, INF);
		for(int i = 0; i < (int)v.size(); i++) seg[i+cap] = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = min(seg[2*i], seg[2*i+1]);
	}
	int qry(int l, int r, int a, int b, int i){
		if(l <= a && b <= r) return seg[i];
		if(b < l || r < a) return INF;
		int m = (a+b)/2;
		return min(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
	}
	int qry(int l, int r){return qry(l, r, 1, cap, 1);}
	void upd(int i, int v){
		i += cap;
		seg[i] = v;
		while(i > 1){
			i /= 2;
			seg[i] = min(seg[2*i], seg[2*i+1]);
		}
	}
};
struct MaxSeg{
	vector<int> seg;
	int cap;
	void init(vector<int> v){
		for(cap = 1; cap < (int)v.size(); cap *= 2);
		seg.resize(2*cap, -INF);
		for(int i = 0; i < (int)v.size(); i++) seg[i+cap] = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = max(seg[2*i], seg[2*i+1]);
	}
	int qry(int l, int r, int a, int b, int i){
		if(l <= a && b <= r) return seg[i];
		if(b < l || r < a) return -INF;
		int m = (a+b)/2;
		return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
	}
	int qry(int l, int r){return qry(l, r, 1, cap, 1);}
	void upd(int i, int v){
		i += cap;
		seg[i] = v;
		while(i > 1){
			i /= 2;
			seg[i] = max(seg[2*i], seg[2*i+1]);
		}
	}
};

int n, W, H;
vector<int> r, c;
vector<bool> mem;
int ans = 0;
MinSeg scmi, srmi;
MaxSeg scma, srma;

vector<set<int>> byR, byC;
vector<int> fr, fc;

void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
	H = h, W = w;
	n = H*W;
	r = R;
	c = C;
	if(H <= 1000 && W <= 1000){
		byR.resize(H);
		byC.resize(W);
		fr.assign(H, -1);
		fc.assign(W, -1);
		for(int i = 0; i < n; i++){
			byR[r[i]].insert(i), byC[c[i]].insert(i);
			if(fr[r[i]] == -1) fr[r[i]] = i;
			if(fc[c[i]] == -1) fc[c[i]] = i;
		}
	}
	else{
		scmi.init(c);
		scma.init(c);
		srmi.init(r);
		srma.init(r);
		mem.resize(n);
		int cmi = INF, cma = -INF, rmi = INF, rma = -INF;
		for(int i = 0; i < n; i++){
			cmi = min(cmi, c[i]);
			cma = max(cma, c[i]);
			rmi = min(rmi, r[i]);
			rma = max(rma, r[i]);
			if((cma-cmi+1)*(rma-rmi+1) == i+1) ans++, mem[i] = true;
		}
	}
}

int swap_seats(int a, int b) {
	if(a > b) swap(a, b);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	if(H <= 1000 && W <= 1000){
		byR[r[a]].erase(b);
		byR[r[a]].insert(a);
		byR[r[b]].erase(a);
		byR[r[b]].insert(b);

		byC[c[a]].erase(b);
		byC[c[a]].insert(a);
		byC[c[b]].erase(a);
		byC[c[b]].insert(b);
		
		fr[r[a]] = *byR[r[a]].begin();
		fr[r[b]] = *byR[r[b]].begin();
		fc[c[a]] = *byC[c[a]].begin();
		fc[c[b]] = *byC[c[b]].begin();

		vector<int> ncmi(W), ncma(W), nrmi(H), nrma(H);
		int val = INF;
		for(int i = 0; i < W; i++){
			ncmi[i] = val;
			val = min(val, fc[i]);
		}
		val = INF;
		for(int i = W-1; i >= 0; i--){
			ncma[i] = val;
			val = min(val, fc[i]);
		}
		val = INF;
		for(int i = 0; i < H; i++){
			nrmi[i] = val;
			val = min(val, fr[i]);
		}
		val = INF;
		for(int i = H-1; i >= 0; i--){
			nrma[i] = val;
			val = min(val, fr[i]);
		}

		ans = 1;
		int cmi = c[0], cma = c[0], rmi = r[0], rma = r[0];
		while(true){
			int j = min(min(ncmi[cmi], ncma[cma]), min(nrmi[rmi], nrma[rma]));
			if(j == INF) break;
			cmi = min(cmi, c[j]);
			cma = max(cma, c[j]);
			rmi = min(rmi, r[j]);
			rma = max(rma, r[j]);
			int k = min(min(ncmi[cmi], ncma[cma]), min(nrmi[rmi], nrma[rma]));
			if(k == INF || (rma-rmi+1)*(cma-cmi+1) == k) ans++;
		}
		return ans;
	}
	else{
		scmi.upd(a, c[a]);
		scma.upd(a, c[a]);
		srmi.upd(a, r[a]);
		srma.upd(a, r[a]);
		scmi.upd(b, c[b]);
		scma.upd(b, c[b]);
		srmi.upd(b, r[b]);
		srma.upd(b, r[b]);
		int cmi = scmi.qry(1, a), cma = scma.qry(1, a), rmi = srmi.qry(1, a), rma = srma.qry(1, a);
		for(int i = a; i < b; i++){
			cmi = min(cmi, c[i]);
			cma = max(cma, c[i]);
			rmi = min(rmi, r[i]);
			rma = max(rma, r[i]);
			bool ok = ((cma-cmi+1)*(rma-rmi+1) == i+1);
			if(mem[i] && !ok) ans--;
			if(!mem[i] && ok) ans++;
			mem[i] = ok;
		}
		return ans;
	}
}

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