Submission #108688

#	Time	Username	Problem	Language	Result	Execution time	Memory
108688		ryansee	New Home (APIO18_new_home)	C++14	80 / 100	4844 ms	131172 KiB

new_home

#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update> pbds_set;
#define llabs abs
#define sdb __attribute__((optimize("-Ofast"), target("arch=sandybridge")))
ll n, q, k;
tuple <ll, ll, ll, ll, ll> A[MAXN]; // l, type, a, b, i
spi Q[MAXN];
ll ans[MAXN];
multiset <ll> ms[MAXN];
priority_queue <pi, vector<pi>,greater<pi>> pq;
void st1_2() {
    sort(Q,Q+q); sort(A,A+n, [] (tuple<ll,ll,ll,ll,ll>x,tuple<ll,ll,ll,ll,ll>y) { return get<2>(x) < get<2>(y); });
	ll co = 0;
	FOR(i,0,q) {
		ll t = Q[i].f, l = Q[i].s.f, ind = Q[i].s.s;
		while(co < n && t >= get<2>(A[co])) {
			ms[get<1>(A[co])].ins(get<0>(A[co]));
			pq.ph(pi(get<3>(A[co]),co));++co;
		}
		while(pq.size() && pq.top().f < t) ms[get<1>(A[pq.top().s])].erase(ms[get<1>(A[pq.top().s])].find(get<0>(A[pq.top().s]))), pq.pop();
		ll anss = -1;
		FOR(i,1,k+1) {
			if(ms[i].empty()) { anss=INF; continue; }
			auto itr = ms[i].lower_bound(l);
			ll best = INF;
			if(itr != ms[i].end()) best=min(best, *itr-l);
			if(itr == ms[i].begin());
			else {
				--itr;
				best=min(best, l-*itr);
			}
// 			assert(best != LLINF);
			anss=max(anss,best);
		}
		if(anss==INF) anss=-1;
		ans[ind]=anss;
	}
	FOR(i,0,q) cout << ans[i] << '\n';
}
map <ll, ll> mp; // x, y
multiset<ll>types[MAXN];
ll STORECO[MAXN];
void check_removal_neg(map<ll,ll>::iterator itr) { 
	while(itr != mp.end()) {
			auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
			if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
			else { break; }
			assert(val == itr->f);
	}
}
void add_neg(ll xx, ll val) {
	mp[xx] = max(mp[xx],val); 
	auto itr = mp.lower_bound(xx);
	while(itr != mp.end()) {
			auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
			if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
			else { break; }
			assert(val == itr->f);
	}
	if(itr!=mp.begin())check_removal_neg(prev(itr));
	return;
}
bool remove_neg(ll &co, ll time) {
	while(co < n && get<3>(A[co]) < time) {
		ll l,type,a,b,ii; tie(l,type,a,b,ii)=A[co]; ++co;
		STORECO[type] --;
		if(STORECO[type] <= 0) return 0;
		auto itr = types[type].lower_bound(l);//assert(itr!=types[type].end());
		if(itr == types[type].begin()) {
		    assert(next(itr)!=types[type].end());
			add_neg(1, *next(itr)-1);
		} else if(next(itr) != types[type].end()) {
			add_neg(((*next(itr) + *prev(itr) + 1)/2), llabs( ((*next(itr) + *prev(itr) + 1)/2) - *next(itr) ));
		}
		types[type].erase(itr);
	}
	return 1;
}
void check_removal_pos(map<ll,ll>::iterator itr) {
	while(itr!=mp.begin()) {
			auto itr2 = prev(itr); ll val = itr->f;
			if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
			else break;
			assert(val==itr->f);
	}
	return;
}
void add_pos(ll xx, ll val) {
	mp[xx]=max(mp[xx],val);
	auto itr = mp.lower_bound(xx);
	while(itr!=mp.begin()) {
			auto itr2 = prev(itr); ll val = itr->f;
			if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
			else break;
			assert(val==itr->f);
	}
	if(next(itr) != mp.end()) check_removal_pos(next(itr));
	return;
}
bool remove_pos(ll &co, ll time) {
	while(co < n && get<3>(A[co]) < time) {
		ll l,type,a,b,ii; tie(l,type,a,b,ii)=A[co]; ++co;
		STORECO[type] --;
		if(STORECO[type]<=0) return 0;
		auto itr = types[type].lower_bound(l); //assert(itr!=types[type].end());
		if(itr == prev(types[type].end())) {
			add_pos(INF, INF-*prev(itr));
		} else if(itr != types[type].begin()) {
			add_pos(((*next(itr) + *prev(itr))/2), llabs( ((*next(itr) + *prev(itr))/2) - *prev(itr) ));
		}
		types[type].erase(itr);
	}	
	return 1;
}
void st3_4() {
	sort(Q,Q+q);
	sort(A,A+n,[](tuple<ll,ll,ll,ll,ll>x,tuple<ll,ll,ll,ll,ll>y) { return get<3>(x) < get<3>(y); });
	FOR(i,0,n) {
		types[get<1>(A[i])].ins(get<0>(A[i])); STORECO[get<1>(A[i])]++; // assert(!duplicate[get<0>(A[i])]); duplicate[get<0>(A[i])] = 1; 
	}
	FOR(K,1,k+1) {
		/*sort(all(types[K])); types[K].resize(unique(all(types[K]))-types[K].begin());*/ if(types[K].empty()) { FOR(i,0,q) cout << "-1\n"; exit(0); }
		for(auto i = next(types[K].begin()); i != types[K].end(); i++) {
			mp[(*i+*prev(i)+1)/2] = max(mp[(*i+*prev(i)+1)/2],llabs(*i-(*i+*prev(i)+1)/2));
		}
		mp[1]=max(mp[1],*types[K].begin()-1);
	}
	for(auto itr = mp.begin(); itr != mp.end(); itr ++) {
		while(itr != mp.end()) {
			auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
			if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
			else { break; }
			assert(val == itr->f);
		}
	}
	ll co = 0; bool stillcan = 1;
	FOR(i,0,q) { if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
		ll l = Q[i].s.f, t = Q[i].f; stillcan &= remove_neg(co,t); if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
		auto itr = mp.upper_bound(l);
		assert(itr != mp.begin()); // even if size is one, itr will be ms.end()
		--itr;
		ans[Q[i].s.s] = itr->s - (l-itr->f);
	}
	mp.clear(); mmst(STORECO,0); FOR(i,1,k+1) types[i].clear(); FOR(i,0,n) { types[get<1>(A[i])].ins(get<0>(A[i])); STORECO[get<1>(A[i])]++; }
	FOR(K,1,k+1) {
		for(auto i = types[K].begin(); i != prev(types[K].end()); i ++) {
			mp[(*i+*next(i))/2] = max(mp[(*i+*next(i))/2],llabs((*i+*next(i))/2-*i));
		}
		mp[INF]=max(mp[INF],INF-(*--types[K].end()));
	}
	for(auto itr = mp.begin(); itr != mp.end(); itr ++) {
		while(itr!=mp.begin()) {
			auto itr2 = prev(itr); ll val = itr->f;
			if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
			else break;
			assert(val==itr->f);
		}
	}
	co = 0;stillcan = 1;
	FOR(i,0,q) { if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
		ll l = Q[i].s.f, t = Q[i].f; stillcan &= remove_pos(co,t); if(!stillcan) { ans[Q[i].s.s] = -INF; continue; } 
		auto itr = mp.lower_bound(l);
// 		assert(itr != mp.end());
		ans[Q[i].s.s] = max(ans[Q[i].s.s], itr->s - (itr->f-l));
	}
	FOR(i,0,q)if(ans[i]==-INF){ans[i]=-1;}
	FOR(i,0,q) cout << ans[i] << '\n';
}
ll rndm = 5;
// struct node {
// 	int s,e,m;
// 	pbds_set v;
// 	node *l, *r;
// 	node(ll _S, ll _E) {
// 		s = _S, e = _E, m = (s+e)/2;
// // 		v.clear();
// 		if(s!=e){
// 			l = new node(s,m);
// 			r = new node(m+1,e);
// 		}
// 	}
// 	void sdb open(ll x, ll nv) {
// 		v.ins(pi(nv,rndm++));
// 		if(s==e) return;
// 		if(x>m) r->open(x,nv);
// 		else l->open(x,nv);
// 	}
// 	void sdb close(ll x, ll nv) {
// 		v.erase(v.lower_bound(pi(nv,0)));
// 		if(s==e) return;
// 		if(x>m) r->close(x,nv);
// 		else l->close(x,nv);
// 	}
// 	ll sdb rmq(ll x, ll y, ll nv) {
// 		if(s==x&&e==y) { return val(nv); }
// 		if(x > m) return r->rmq(x,y,nv);
// 		else if(y <= m) return l->rmq(x,y,nv);
// 		else return l->rmq(x,m,nv) + r->rmq(m+1,y,nv);
// 	}
// 	inline ll sdb val(ll x) {
// 		return (v.order_of_key(pi(x,0)));
// 	}
// // 	void degug() {
// // 		if(v.empty()) return;
// // // 		if(s==e) { assert(siz(v)==1); cerr << s << ' ' << v[0] << '\n'; return; }
// // 		l->degug();
// // 		r->degug();
// // 	}
// } *seg;
pbds_set fw[MAXN];
void open(ll x, ll nv) {
	++ x;
	for(; x <= n; x+=x&(-x)) fw[x].ins(pi(nv,rndm++));
}
void close(ll x, ll nv) {
	++ x;
	for(; x <= n; x+=x&(-x)) fw[x].erase(fw[x].lower_bound(pi(nv,0)));
}
ll query(ll x, ll nv) {
    ll res = 0;
    for(; x; x-=x&(-x)) {
        res += fw[x].order_of_key(pi(nv,0));
    }
    return res;
}
ll rmq(ll x, ll y, ll nv) {
    ++x,++y;
    return query(y,nv) - query(x-1,nv);
}
vector<ll>d;
inline ll sdb solve5(ll l) {
	ll st = -1, en = max(d.back()-l+2,l-d[0]+2), mid = 0;
	while(en-st > 1) {
		mid = (st+en)>>1ll;
		ll lower = lbd(d,l-mid)-d.begin();
		ll upper = ubd(d,l+mid)-d.begin()-1;
		if(lower<=upper&&rmq(lower,upper,lower) >= k) en = mid;
		else st = mid;
	}
	return en;
}
inline void sdb rem(ll k, multiset<ll>::iterator itr) {
	if(itr == types[k].begin()||itr==types[k].end()) return; 
	close(*itr, *prev(itr));
}
inline void sdb add(ll k, multiset<ll>::iterator itr) {
	if(itr == types[k].begin()||itr==types[k].end()) return;
	open(*itr, *prev(itr));
}
inline void sdb st5() {
	sort(Q,Q+q);  FOR(i,0,n) d.pb(get<0>(A[i])); sort(all(d)); d.resize(unique(all(d))-d.begin());FOR(i,0,n) { get<4>(A[i]) = lbd(d,get<0>(A[i]))-d.begin(); }
	sort(A,A+n,[](tuple<ll,ll,ll,ll,ll>x,tuple<ll,ll,ll,ll,ll>y) { return get<2>(x) < get<2>(y); });
	ll co = 0; priority_queue <pi, vector<pi>, greater<pi>> ms; // seg = new node(0, n-1);
	FOR(i,1,k+1) types[i].ins(-INF);
	FOR(i,0,q) {
		ll t = Q[i].f, l = Q[i].s.f, ind = Q[i].s.s;
		while(co < n && get<2>(A[co]) <= t) {
		    if(get<3>(A[co]) < t) { ++co; continue; }
			ll type = get<1>(A[co]);
			ll i = get<4>(A[co]);
			auto itr = types[type].lower_bound(i);
			if(itr != types[type].end()) { rem(type, itr); }
			types[type].ins(i);
			itr = types[type].lower_bound(i);
			add(type, itr);
			add(type, next(itr));
			ms.ph(pi(get<3>(A[co]), co));
			++co;
		}
		while(ms.size() && ms.top().f < t) {
			ll i = get<4>(A[ms.top().s]);
			ll type = get<1>(A[ms.top().s]);
			ms.pop();
			auto itr = types[type].find(i); // assert(itr != types[type].begin()); 
			rem(type,itr); 
			rem(type,next(itr));
			itr = types[type].erase(types[type].find(i));
			add(type, itr);
		}
		ans[ind] = solve5(l);  if(ans[ind]==max(d.back()-l+2,l-d[0]+2)) ans[ind]=-1;
	}
	FOR(i,0,q) cout << ans[i] << '\n';
}
int sdb main()
{ // freopen("int","r",stdin);
	FAST
	cin>>n>>k>>q;
	FOR(i,0,n) {
		ll a,b,c,d;cin>>a>>b>>c>>d;
		A[i]=make_tuple(a,b,c,d,i);
	}
	FOR(i,0,q) {
		ll l,t;
		cin>>l>>t;
		Q[i]=spi(t,pi(l,i));
	}
	if(k<=400&&n<=6*1e4&&q<=6*1e4) { st1_2(); return 0; }
	else if(n > 6*((ll)1e4)) {
	    st3_4(); return 0;
	}
	else { st5(); }
}
/*
 * 
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
* 
* 
*
* to fit st3_4 sol *
4 2 4
3 1 1 10
9 2 1 4
7 2 1 7
4 1 1 10
5 3
5 6
5 9
1 10 
* 
*Ans:
* 2
* 2
* -1
* -1
*/

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