oj.uz

Submission #108218

# Submission time Handle Problem Language Result Execution time Memory
108218 2019-04-28T08:29:07 Z ryansee New Home (APIO18_new_home) C++14
33 / 100
 3982 ms 97596 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30968 KB Output is correct
2 Correct 30 ms 30976 KB Output is correct
3 Correct 27 ms 28544 KB Output is correct
4 Incorrect 34 ms 30968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30968 KB Output is correct
2 Correct 30 ms 30976 KB Output is correct
3 Correct 27 ms 28544 KB Output is correct
4 Incorrect 34 ms 30968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 95032 KB Output is correct
2 Correct 2016 ms 96604 KB Output is correct
3 Correct 659 ms 80284 KB Output is correct
4 Correct 1367 ms 92528 KB Output is correct
5 Correct 2221 ms 96148 KB Output is correct
6 Correct 1845 ms 96444 KB Output is correct
7 Correct 352 ms 80220 KB Output is correct
8 Correct 861 ms 92692 KB Output is correct
9 Correct 1285 ms 96864 KB Output is correct
10 Correct 1377 ms 97596 KB Output is correct
11 Correct 1118 ms 95864 KB Output is correct
12 Correct 1204 ms 97384 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2248 ms 97556 KB Output is correct
2 Correct 766 ms 68600 KB Output is correct
3 Correct 3394 ms 96384 KB Output is correct
4 Correct 606 ms 78108 KB Output is correct
5 Correct 1293 ms 93048 KB Output is correct
6 Correct 1251 ms 90692 KB Output is correct
7 Correct 3982 ms 96528 KB Output is correct
8 Correct 3909 ms 96348 KB Output is correct
9 Correct 672 ms 79532 KB Output is correct
10 Correct 1558 ms 93512 KB Output is correct
11 Correct 2131 ms 97220 KB Output is correct
12 Correct 2650 ms 97164 KB Output is correct
13 Correct 1200 ms 94432 KB Output is correct
14 Correct 1267 ms 93712 KB Output is correct
15 Correct 1612 ms 95452 KB Output is correct
16 Correct 2048 ms 96696 KB Output is correct
17 Correct 1549 ms 95072 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30968 KB Output is correct
2 Correct 30 ms 30976 KB Output is correct
3 Correct 27 ms 28544 KB Output is correct
4 Incorrect 34 ms 30968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30968 KB Output is correct
2 Correct 30 ms 30976 KB Output is correct
3 Correct 27 ms 28544 KB Output is correct
4 Incorrect 34 ms 30968 KB Output isn't correct
5 Halted 0 ms 0 KB -