제출 #515202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515202		amunduzbaev	Golf (JOI17_golf)	C++14	100 / 100	2876 ms	285224 KiB

golf

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

#define ar array

const int N = 2e5 + 7;

struct seg{
	int t, x, l, r;
	bool operator == (seg b){
		return (t == b.t && x == b.x && l == b.l && r == b.r);
	}
};

struct ST{
	set<ar<int, 2>> tree[N * 4];
	
	void add(int l, int r, ar<int, 2> v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x].insert(v);
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x<<1), add(l, r, v, m+1, rx, x<<1|1);
	}

	void del(int l, int r, ar<int, 2> v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x].erase(v);
			return;
		} int m = (lx + rx) >> 1;
		del(l, r, v, lx, m, x<<1), del(l, r, v, m+1, rx, x<<1|1);
	}
	
	int get(int i, int l, int r, int lx = 0, int rx = N, int x = 1){
		auto it = tree[x].lower_bound({l, -1});
		if(it != tree[x].end() && (*it)[0] <= r) return (*it)[1];
		if(lx == rx) return -1;
		int m = (lx + rx) >> 1;
		if(i <= m) return get(i, l, r, lx, m, x<<1);
		else return get(i, l, r, m+1, rx, x<<1|1);
	}
}tree[2];

struct ST2{
	int tree[N * 4];
	void sett(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		sett(l, r, v, lx, m, x<<1), sett(l, r, v, m+1, rx, x<<1|1);
	}
	
	int get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x];
		int m = (lx + rx) >> 1;
		if(i <= m) return max(tree[x], get(i, lx, m, x<<1));
		else return max(tree[x], get(i, m+1, rx, x<<1|1));
	}
}tr;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	ar<int, 2> a, b; cin>>a[0]>>a[1]>>b[0]>>b[1];
	int n; cin>>n;
	vector<ar<int, 4>> p(n);
	for(int i=0;i<n;i++){
		cin>>p[i][0]>>p[i][2]>>p[i][1]>>p[i][3];
	}
	{
		vector<ar<int, 2>> tt;
		for(int i=0;i<n;i++){
			tt.push_back({p[i][0], i<<1});
			tt.push_back({p[i][2], i<<1|1});
		} 
		tt.push_back({a[0], -1});
		tt.push_back({b[0], -2});
		sort(tt.begin(), tt.end());
		
		int last = 0;
		for(int i=0;i<(int)tt.size();){
			int j = i;
			while(j < (int)tt.size() && tt[i][0] == tt[j][0]){
				if(tt[j][1]>=0) p[tt[j][1]>>1][(tt[j][1]&1) << 1] = last;
				else if(tt[j][1]==-1) a[0] = last;
				else b[0] = last;
				j++;
			} i = j, last++;
		} tt.clear();
		
		for(int i=0;i<n;i++){
			tt.push_back({p[i][1], i<<1});
			tt.push_back({p[i][3], i<<1|1});
		} 
		tt.push_back({a[1], -1});
		tt.push_back({b[1], -2});
		
		sort(tt.begin(), tt.end());
		last = 0;
		for(int i=0;i<(int)tt.size();){
			int j = i;
			while(j < (int)tt.size() && tt[j][0] == tt[i][0]){
				if(tt[j][1] >= 0) p[tt[j][1]>>1][(tt[j][1]&1)<<1|1] = last;
				else if(tt[j][1] == -1) a[1] = last;
				else b[1] = last;
				j++;
			} last++, i = j;
		}
	}
	
	//~ for(int i=0;i<n;i++){
		//~ for(int t=0;t<4;t++) cout<<p[i][t]<<" ";
		//~ cout<<endl;
	//~ } 
	//~ cout<<a[0]<<" "<<a[1]<<", "<<b[0]<<" "<<b[1]<<endl;
	//~ cout<<endl;
	vector<ar<int, 4>> lx(n), rx(n);
	ar<int, 2> _l = {-1, -1}, _r = {-1, -1};
	ar<int, 2> l_ = {-1, -1}, r_ = {-1, -1};
	
	{
		vector<int> pp(n); iota(pp.begin(), pp.end(), 0);
		sort(pp.begin(), pp.end(), [&](int i, int j){
			return (p[i][2] < p[j][2]);
		});
		
		for(auto i : pp){
			if(p[i][2] > a[0] && _l[1] == -1) _l[1] = tr.get(a[1]);
			if(p[i][2] > b[0] && l_[1] == -1) l_[1] = tr.get(b[1]);
			lx[i][1] = tr.get(p[i][1]);
			lx[i][3] = tr.get(p[i][3]);
			if(p[i][1] + 1 < p[i][3]) 
				tr.sett(p[i][1] + 1, p[i][3] - 1, p[i][2]);
		} 
		if(_l[1] == -1) _l[1] = tr.get(a[1]);
		if(l_[1] == -1) l_[1] = tr.get(b[1]);
		memset(tr.tree, 128, sizeof tr.tree);
		
		sort(pp.begin(), pp.end(), [&](int i, int j){
			return (p[i][0] > p[j][0]);
		});
		
		for(auto i : pp){
			if(p[i][0] < a[0] && _r[1] == -1) _r[1] = min(N, -tr.get(a[1]));
			if(p[i][0] < b[0] && r_[1] == -1) r_[1] = min(N, -tr.get(b[1]));
			rx[i][1] = min(N, -tr.get(p[i][1]));
			rx[i][3] = min(N, -tr.get(p[i][3]));
			if(p[i][1] + 1 < p[i][3]) 
				tr.sett(p[i][1] + 1, p[i][3] - 1, -p[i][0]);
		} 
		if(_r[1] == -1) _r[1] = min(N, -tr.get(a[1]));
		if(r_[1] == -1) r_[1] = min(N, -tr.get(b[1]));
		memset(tr.tree, 0, sizeof tr.tree);
		
		sort(pp.begin(), pp.end(), [&](int i, int j){
			return (p[i][3] < p[j][3]);
		});
		
		for(auto i : pp){
			if(p[i][3] > a[1] && _l[0] == -1) _l[0] = tr.get(a[0]);
			if(p[i][3] > b[1] && l_[0] == -1) l_[0] = tr.get(b[0]);
			lx[i][0] = tr.get(p[i][0]);
			lx[i][2] = tr.get(p[i][2]);
			if(p[i][0] + 1 < p[i][2]) 
				tr.sett(p[i][0] + 1, p[i][2] - 1, p[i][3]);
		} 
		if(_l[0] == -1) _l[0] = tr.get(a[0]);
		if(l_[0] == -1) l_[0] = tr.get(b[0]);
		memset(tr.tree, 128, sizeof tr.tree);
		
		sort(pp.begin(), pp.end(), [&](int i, int j){
			return (p[i][1] > p[j][1]);
		});
		
		for(auto i : pp){
			if(p[i][1] < a[1] && _r[0] == -1) _r[0] = min(N, -tr.get(a[0]));
			if(p[i][1] < b[1] && r_[0] == -1) r_[0] = min(N, -tr.get(b[0]));
			rx[i][0] = min(N, -tr.get(p[i][0]));
			rx[i][2] = min(N, -tr.get(p[i][2]));
			if(p[i][0] + 1 < p[i][2]) 
				tr.sett(p[i][0] + 1, p[i][2] - 1, -p[i][1]);
		} 
		if(_r[0] == -1) _r[0] = min(N, -tr.get(a[0]));
		if(r_[0] == -1) r_[0] = min(N, -tr.get(b[0]));
	}
	//~ cout<<_l[0]<<" "<<_r[0]<<"\n";
	vector<seg> tt;
	
	for(int i=0;i<n;i++){
		for(int t=0;t<4;t++){
			tt.push_back({t&1, p[i][t], lx[i][t], rx[i][t]});
		}
	}
	
	tt.push_back({0, a[0], _l[0], _r[0]});
	tt.push_back({1, a[1], _l[1], _r[1]});
	tt.push_back({0, b[0], l_[0], r_[0]});
	tt.push_back({1, b[1], l_[1], r_[1]});
	
	int in = 0;
	for(auto x : tt){
		tree[x.t].add(x.l, x.r, {x.x, in}); in++;
	}
	
	vector<int> d((n + 1) * 4, 1e9);
	vector<int> tmp; 
	tmp.push_back(n * 4);
	tmp.push_back(n * 4 + 1);
	in = 0;
	for(auto x : tt){
		if(x == tt[tmp[0]] || x == tt[tmp[1]]){
			tree[x.t].del(x.l, x.r, {x.x, in}), 
			d[in] = 1;
		}
		in++;
	}
	
	for(int j=0;j<4*n;j++){
		vector<int> nw;
		//~ for(auto i : tmp) cout<<tt[i].t<<" "<<tt[i].x<<" "<<tt[i].l<<" "<<tt[i].r<<"\n";
		for(auto i : tmp){
			int in = tree[tt[i].t ^ 1].get(tt[i].x, tt[i].l, tt[i].r);
			while(~in){
				tree[tt[in].t].del(tt[in].l, tt[in].r, {tt[in].x, in});
				d[in] = d[i] + 1;
				nw.push_back(in);
				in = tree[tt[i].t ^ 1].get(tt[i].x, tt[i].l, tt[i].r);
			}
		} swap(tmp, nw);
		//~ cout<<"\n";
	}
	
	cout<<min(d[n * 4 + 2], d[n * 4 + 3])<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70