Submission #565317

#	Time	Username	Problem	Language	Result	Execution time	Memory
565317		S2speed	New Home (APIO18_new_home)	C++17	0 / 100	5105 ms	994456 KiB

new_home

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 3e5 + 17 , inf = 1e10;

pll operator + (pll a , pll b){
	pll res;
	res.first = a.first + b.first;
	res.second = a.second + b.second;
	return res;
}

void operator += (pll &a , pll b){
	a = a + b;
	return;
}

vector<ll> v;

struct segtree {

	ll sz = 1;
	pll def = {0 , 0};
	vector<set<pll>> van;
	vector<set<pll , greater<pll>>> vax;
	set<pll> sn;
	set<pll , greater<pll>> sx;

	void init(ll n){
		while(sz < n) sz <<= 1;
		sn.insert({inf , -1});
		sx.insert({-inf , -1});
		van.assign(sz << 1 , sn);
		vax.assign(sz << 1 , sx);
		return;
	}

	void add(ll l , ll r , pll k , bool c , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			if(c){
				vax[x].insert(k);
			} else {
				van[x].insert(k);
//				cout<<(*van[x].begin()).first<<' '<<k.first<<"f\n";
			}
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		add(l , r , k , c , ln , lx , m); add(l , r , k , c , rn , m , rx);
		return;
	}

	void add(ll l , ll r , pll k , bool c){
		ll lv = upper_bound(all(v) , l) - v.begin() - 1 , rv = lower_bound(all(v) , r) - v.begin();
//		cout<<l<<' '<<r<<" --- ";
//		cout<<lv<<' '<<rv<<'\n';
//		cout<<v[4]<<'\n';
		if(lv == rv) return;
		add(lv , rv , k , c , 0 , 0 , sz);
		return;
	}

	void del(ll l , ll r , pll k , bool c , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			if(c){
				vax[x].erase(k);
			} else {
				van[x].erase(k);
			}
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		del(l , r , k , c , ln , lx , m); del(l , r , k , c , rn , m , rx);
		return;
	}

	void del(ll l , ll r , pll k , bool c){
		ll lv = upper_bound(all(v) , l) - v.begin() - 1 , rv = lower_bound(all(v) , r) - v.begin();
		if(lv == rv) return;
		del(lv , rv , k , c , 0 , 0 , sz);
		return;
	}

	pll cal(ll i , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			ll h = (*vax[x].begin()).first , o = (*van[x].begin()).first;
			return {o , h};
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pll a;
		if(i < m){
			a = cal(i , ln , lx , m);
		} else {
			a = cal(i , rn , m , rx);
		}
		ll h = max((*vax[x].begin()).first , a.second) , o = min((*van[x].begin()).first , a.first);
		return {o , h};
	}

	pll cal(ll i){
		ll iv = lower_bound(all(v) , i) - v.begin();
		return cal(iv , 0 , 0 , sz);
	}

};

segtree st;
ll l[maxn] , r[maxn] , x[maxn] , c[maxn] , y[maxn] , t[maxn] , ans[maxn] , cnt[maxn];
set<pll> s[maxn] , cs;
vector<ll> vt , dl[maxn] , ad[maxn] , qu[maxn];

void add(ll i){
	cs.erase({cnt[c[i]]++ , c[i]});
	cs.insert({cnt[c[i]] , c[i]});
//	cout<<i<<' '<<c[i]<<' '<<cnt[c[i]]<<'\n';
	s[c[i]].insert({x[i] , i});
	auto it = s[c[i]].lower_bound({x[i] , i});
	ll pr , nx;
	pll p , n;
	it++;
	n = *it;
	nx = (*it).first;
	it--; it--;
	p = *it;
	pr = (*it).first;
	ll mp = (pr + x[i] + 1) / 2 , mn = (x[i] + nx + 1) / 2 , m = (pr + nx + 1) / 2;
	pll r = {x[i] , i};
	st.del(pr , m , p , 0);
	st.del(m , nx , n , 1);
	if(p.first != -inf) st.add(pr , mp , p , 0);
	st.add(mp , x[i] , r , 1);
	st.add(x[i] , mn , r , 0);
//	cout<<mp<<' '<<x[i]<<' '<<mn<<'\n';
	if(n.first != inf) st.add(mn , nx , n , 1);
	return;
}

void del(ll i){
//	cout<<"del "<<i<<' '<<c[i]<<'\n';
	cs.erase({cnt[c[i]]-- , c[i]});
	cs.insert({cnt[c[i]] , c[i]});
	auto it = s[c[i]].lower_bound({x[i] , i});
	ll pr , nx;
	pll p , n;
	it++;
	n = *it;
	nx = (*it).first;
	it--; it--;
	p = *it;
	pr = (*it).second;
	s[c[i]].erase({x[i] , i});
	ll m = (nx + pr + 1) / 2 , mp = (pr + x[i] + 1) / 2 , mn = (x[i] + nx + 1) / 2;
	pll r = {x[i] , i};
	st.del(pr , mp , p , 0);
	st.del(mp , x[i] , r , 1);
	st.del(x[i] , mn , r , 0);
	st.del(mn , nx , n , 1);
	if(p.first != -inf) st.add(pr , m , p , 0);
	if(n.first != inf) st.add(m , nx , n , 1);
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n , k , q;
	cin>>n>>k>>q;
	for(ll i = 0 ; i < n ; i++){
		cin>>x[i]>>c[i]>>l[i]>>r[i]; r[i]++; c[i]--;
		v.push_back(x[i]);
		vt.push_back(l[i]); vt.push_back(r[i]);
	}
	for(ll i = 0 ; i < q ; i++){
		cin>>y[i]>>t[i];
		v.push_back(y[i]);
		vt.push_back(t[i]);
	}
	sort(all(v));
	v.resize(distance(v.begin() , unique(all(v))));
//	for(auto i : v){
//		cout<<i<<' ';
//	}
//	cout<<'\n';
	ll vs = sze(v);
	st.init(vs);
	for(ll i = 0 ; i < k ; i++){
		s[i].insert({-inf , -1}); s[i].insert({inf , -1});
	}
	sort(all(vt));
	vt.resize(distance(vt.begin() , unique(all(vt))));
	for(ll i = 0 ; i < n ; i++){
		l[i] = lower_bound(all(vt) , l[i]) - vt.begin();
		ad[l[i]].push_back(i);
		r[i] = lower_bound(all(vt) , r[i]) - vt.begin();
		dl[r[i]].push_back(i);
	}
	for(ll i = 0 ; i < q ; i++){
		t[i] = lower_bound(all(vt) , t[i]) - vt.begin();
		qu[t[i]].push_back(i);
	}
	ll ts = sze(vt);
	for(ll i = 0 ; i < k ; i++){
		cs.insert({0 , i});
	}
	for(ll i = 0 ; i < ts ; i++){
		for(auto j : ad[i]){
			add(j);
		}
		for(auto j : dl[i]){
			del(j);
		}
		for(auto j : qu[i]){
			if((*(cs.begin())).first == 0){
				ans[j] = -1;
				continue;
			}
			pll h = st.cal(y[j]);
			ans[j] = max(y[j] - h.first , h.second - y[j]);
		}
	}
	for(ll i = 0 ; i < q ; i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

/*
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
*/

/*
1 1 1
100000000 1 1 1
1 1
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20