Submission #108218

#	Time	Username	Problem	Language	Result	Execution time	Memory
108218		ryansee	New Home (APIO18_new_home)	C++14	33 / 100	3982 ms	97596 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
ll n, q, k;
tuple <ll, ll, ll, ll> A[MAXN]; // l, type, a, b
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>x,tuple<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; tie(l,type,a,b)=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; tie(l,type,a,b)=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>x,tuple<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';
}
int 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);
	}
	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&&0) { st1_2(); return 0; }
	else {
	    st3_4(); 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
* 
* 
*
* 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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20