Submission #596962

#	Time	Username	Problem	Language	Result	Execution time	Memory
596962		Lucpp	Seats (IOI18_seats)	C++17	70 / 100	4019 ms	134860 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]);
		}
	}
};
struct RangeSeg{
	vector<pair<int, int>> seg;
	vector<int> lazy;
	int cap;
	pair<int, int> combine(pair<int, int> a, pair<int, int> b){
		if(a > b) swap(a, b);
		if(a.first == b.first) a.second += b.second;
		return a;
	}
	void init(vector<int> v){
		int n = (int)v.size();
		for(int i = 1; i < n; i++) v[i] += v[i-1];
		for(cap = 1; cap < n; cap*=2);
		seg.resize(2*cap, {INF, 1});
		lazy.resize(2*cap, 0);
		for(int i = 0; i < n; i++) seg[i+cap].first = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
	}
	void apply(int v, int i){
		seg[i].first += v;
		lazy[i] += v;
	}
	void push(int i){
		apply(lazy[i], 2*i);
		apply(lazy[i], 2*i+1);
		lazy[i] = 0;
	}
	void upd(int l, int r, int v, int a, int b, int i){
		if(l <= a && b <= r) apply(v, i);
		else if(b < l || r < a) return;
		else{
			push(i);
			int m = (a+b)/2;
			upd(l, r, v, a, m, 2*i);
			upd(l, r, v, m+1, b, 2*i+1);
			seg[i] = combine(seg[2*i], seg[2*i+1]);
		}
	}
	void upd(int l, int r, int v){upd(l, r, v, 1, cap, 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;

vector<int> num, adj;
RangeSeg range;

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 if(H == 1){
		num.resize(n+2, INF);
		adj.resize(n);
		for(int i = 0; i < n; i++) num[c[i]+1] = i;
		for(int i = 1; i <= n; i++){
			adj[num[i]] = 2*(1-(num[i]>num[i-1])-(num[i]>num[i+1]));
		}
		range.init(adj);
	}
	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[b]].erase(a);
		byR[r[a]].insert(a);
		byR[r[b]].insert(b);

		byC[c[a]].erase(b);
		byC[c[b]].erase(a);
		byC[c[a]].insert(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 if(H == 1){
		swap(num[c[a]+1], num[c[b]+1]);
		auto upd = [&](int i){
			if(i == 0 || i == W+1) return;
			int x = 2*(1-(num[i]>num[i-1])-(num[i]>num[i+1]));
			range.upd(num[i]+1, n+1, x-adj[num[i]]);
			adj[num[i]] = x;
		};
		upd(c[a]);
		upd(c[a]+1);
		upd(c[a]+2);
		upd(c[b]);
		upd(c[b]+1);
		upd(c[b]+2);
		ans = range.seg[1].second;
		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: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 0 / 30