Submission #596859

#	Time	Username	Problem	Language	Result	Execution time	Memory
596859		Lucpp	Seats (IOI18_seats)	C++17	17 / 100	4077 ms	76524 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;
vector<int> r, c;
vector<bool> mem;
int ans = 0;
MinSeg scmi, srmi;
MaxSeg scma, srma;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H*W;
	r = R;
	c = C;
	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]);
	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 b = ((cma-cmi+1)*(rma-rmi+1) == i+1);
		if(mem[i] && !b) ans--;
		if(!mem[i] && b) ans++;
		mem[i] = b;
	}
	return ans;
}

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