oj.uz

Submission #108220

# Submission time Handle Problem Language Result Execution time Memory
108220 2019-04-28T08:29:52 Z ryansee New Home (APIO18_new_home) C++14
45 / 100
 4366 ms 86132 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) { 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28548 KB Output is correct
2 Correct 32 ms 28672 KB Output is correct
3 Correct 29 ms 28484 KB Output is correct
4 Correct 35 ms 28600 KB Output is correct
5 Correct 27 ms 28544 KB Output is correct
6 Correct 32 ms 28664 KB Output is correct
7 Correct 27 ms 28544 KB Output is correct
8 Correct 30 ms 28628 KB Output is correct
9 Correct 32 ms 28644 KB Output is correct
10 Correct 26 ms 28544 KB Output is correct
11 Correct 26 ms 28636 KB Output is correct
12 Correct 35 ms 28536 KB Output is correct
13 Correct 27 ms 28536 KB Output is correct
14 Correct 28 ms 28544 KB Output is correct
15 Correct 33 ms 28636 KB Output is correct
16 Correct 32 ms 28536 KB Output is correct
17 Correct 27 ms 28636 KB Output is correct
18 Correct 78 ms 28632 KB Output is correct
19 Correct 28 ms 28588 KB Output is correct
20 Correct 29 ms 28560 KB Output is correct
21 Correct 30 ms 28660 KB Output is correct
22 Correct 36 ms 28536 KB Output is correct
23 Correct 33 ms 28648 KB Output is correct
24 Correct 32 ms 28636 KB Output is correct
25 Correct 29 ms 28516 KB Output is correct
26 Correct 29 ms 28636 KB Output is correct
27 Correct 28 ms 28644 KB Output is correct
28 Correct 33 ms 28564 KB Output is correct
29 Correct 29 ms 28528 KB Output is correct
30 Correct 30 ms 28552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28548 KB Output is correct
2 Correct 32 ms 28672 KB Output is correct
3 Correct 29 ms 28484 KB Output is correct
4 Correct 35 ms 28600 KB Output is correct
5 Correct 27 ms 28544 KB Output is correct
6 Correct 32 ms 28664 KB Output is correct
7 Correct 27 ms 28544 KB Output is correct
8 Correct 30 ms 28628 KB Output is correct
9 Correct 32 ms 28644 KB Output is correct
10 Correct 26 ms 28544 KB Output is correct
11 Correct 26 ms 28636 KB Output is correct
12 Correct 35 ms 28536 KB Output is correct
13 Correct 27 ms 28536 KB Output is correct
14 Correct 28 ms 28544 KB Output is correct
15 Correct 33 ms 28636 KB Output is correct
16 Correct 32 ms 28536 KB Output is correct
17 Correct 27 ms 28636 KB Output is correct
18 Correct 78 ms 28632 KB Output is correct
19 Correct 28 ms 28588 KB Output is correct
20 Correct 29 ms 28560 KB Output is correct
21 Correct 30 ms 28660 KB Output is correct
22 Correct 36 ms 28536 KB Output is correct
23 Correct 33 ms 28648 KB Output is correct
24 Correct 32 ms 28636 KB Output is correct
25 Correct 29 ms 28516 KB Output is correct
26 Correct 29 ms 28636 KB Output is correct
27 Correct 28 ms 28644 KB Output is correct
28 Correct 33 ms 28564 KB Output is correct
29 Correct 29 ms 28528 KB Output is correct
30 Correct 30 ms 28552 KB Output is correct
31 Correct 3688 ms 39428 KB Output is correct
32 Correct 151 ms 35184 KB Output is correct
33 Correct 312 ms 36952 KB Output is correct
34 Correct 2144 ms 37048 KB Output is correct
35 Correct 1527 ms 39380 KB Output is correct
36 Correct 363 ms 39276 KB Output is correct
37 Correct 222 ms 36008 KB Output is correct
38 Correct 151 ms 35860 KB Output is correct
39 Correct 118 ms 35620 KB Output is correct
40 Correct 114 ms 35556 KB Output is correct
41 Correct 311 ms 35832 KB Output is correct
42 Correct 412 ms 35576 KB Output is correct
43 Correct 361 ms 39016 KB Output is correct
44 Correct 237 ms 35832 KB Output is correct
45 Correct 161 ms 35736 KB Output is correct
46 Correct 107 ms 35612 KB Output is correct
47 Correct 102 ms 35268 KB Output is correct
48 Correct 96 ms 35252 KB Output is correct
49 Correct 111 ms 35448 KB Output is correct
50 Correct 261 ms 35516 KB Output is correct
51 Correct 98 ms 35448 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1533 ms 83240 KB Output is correct
2 Correct 1923 ms 85724 KB Output is correct
3 Correct 644 ms 67960 KB Output is correct
4 Correct 1297 ms 80452 KB Output is correct
5 Correct 2021 ms 85136 KB Output is correct
6 Correct 1833 ms 85452 KB Output is correct
7 Correct 420 ms 68140 KB Output is correct
8 Correct 978 ms 80376 KB Output is correct
9 Correct 1201 ms 84728 KB Output is correct
10 Correct 1401 ms 86132 KB Output is correct
11 Correct 1022 ms 84984 KB Output is correct
12 Correct 1274 ms 85968 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2254 ms 85820 KB Output is correct
2 Correct 769 ms 65756 KB Output is correct
3 Correct 3341 ms 85460 KB Output is correct
4 Correct 603 ms 66164 KB Output is correct
5 Correct 1383 ms 80956 KB Output is correct
6 Correct 1213 ms 78640 KB Output is correct
7 Correct 4366 ms 85652 KB Output is correct
8 Correct 3577 ms 85324 KB Output is correct
9 Correct 620 ms 67204 KB Output is correct
10 Correct 1640 ms 81400 KB Output is correct
11 Correct 2066 ms 84572 KB Output is correct
12 Correct 2705 ms 84976 KB Output is correct
13 Correct 1224 ms 83056 KB Output is correct
14 Correct 1163 ms 82376 KB Output is correct
15 Correct 1574 ms 83352 KB Output is correct
16 Correct 1950 ms 84320 KB Output is correct
17 Correct 1554 ms 83068 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28548 KB Output is correct
2 Correct 32 ms 28672 KB Output is correct
3 Correct 29 ms 28484 KB Output is correct
4 Correct 35 ms 28600 KB Output is correct
5 Correct 27 ms 28544 KB Output is correct
6 Correct 32 ms 28664 KB Output is correct
7 Correct 27 ms 28544 KB Output is correct
8 Correct 30 ms 28628 KB Output is correct
9 Correct 32 ms 28644 KB Output is correct
10 Correct 26 ms 28544 KB Output is correct
11 Correct 26 ms 28636 KB Output is correct
12 Correct 35 ms 28536 KB Output is correct
13 Correct 27 ms 28536 KB Output is correct
14 Correct 28 ms 28544 KB Output is correct
15 Correct 33 ms 28636 KB Output is correct
16 Correct 32 ms 28536 KB Output is correct
17 Correct 27 ms 28636 KB Output is correct
18 Correct 78 ms 28632 KB Output is correct
19 Correct 28 ms 28588 KB Output is correct
20 Correct 29 ms 28560 KB Output is correct
21 Correct 30 ms 28660 KB Output is correct
22 Correct 36 ms 28536 KB Output is correct
23 Correct 33 ms 28648 KB Output is correct
24 Correct 32 ms 28636 KB Output is correct
25 Correct 29 ms 28516 KB Output is correct
26 Correct 29 ms 28636 KB Output is correct
27 Correct 28 ms 28644 KB Output is correct
28 Correct 33 ms 28564 KB Output is correct
29 Correct 29 ms 28528 KB Output is correct
30 Correct 30 ms 28552 KB Output is correct
31 Correct 3688 ms 39428 KB Output is correct
32 Correct 151 ms 35184 KB Output is correct
33 Correct 312 ms 36952 KB Output is correct
34 Correct 2144 ms 37048 KB Output is correct
35 Correct 1527 ms 39380 KB Output is correct
36 Correct 363 ms 39276 KB Output is correct
37 Correct 222 ms 36008 KB Output is correct
38 Correct 151 ms 35860 KB Output is correct
39 Correct 118 ms 35620 KB Output is correct
40 Correct 114 ms 35556 KB Output is correct
41 Correct 311 ms 35832 KB Output is correct
42 Correct 412 ms 35576 KB Output is correct
43 Correct 361 ms 39016 KB Output is correct
44 Correct 237 ms 35832 KB Output is correct
45 Correct 161 ms 35736 KB Output is correct
46 Correct 107 ms 35612 KB Output is correct
47 Correct 102 ms 35268 KB Output is correct
48 Correct 96 ms 35252 KB Output is correct
49 Correct 111 ms 35448 KB Output is correct
50 Correct 261 ms 35516 KB Output is correct
51 Correct 98 ms 35448 KB Output is correct
52 Incorrect 132 ms 40788 KB Output isn't correct
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28548 KB Output is correct
2 Correct 32 ms 28672 KB Output is correct
3 Correct 29 ms 28484 KB Output is correct
4 Correct 35 ms 28600 KB Output is correct
5 Correct 27 ms 28544 KB Output is correct
6 Correct 32 ms 28664 KB Output is correct
7 Correct 27 ms 28544 KB Output is correct
8 Correct 30 ms 28628 KB Output is correct
9 Correct 32 ms 28644 KB Output is correct
10 Correct 26 ms 28544 KB Output is correct
11 Correct 26 ms 28636 KB Output is correct
12 Correct 35 ms 28536 KB Output is correct
13 Correct 27 ms 28536 KB Output is correct
14 Correct 28 ms 28544 KB Output is correct
15 Correct 33 ms 28636 KB Output is correct
16 Correct 32 ms 28536 KB Output is correct
17 Correct 27 ms 28636 KB Output is correct
18 Correct 78 ms 28632 KB Output is correct
19 Correct 28 ms 28588 KB Output is correct
20 Correct 29 ms 28560 KB Output is correct
21 Correct 30 ms 28660 KB Output is correct
22 Correct 36 ms 28536 KB Output is correct
23 Correct 33 ms 28648 KB Output is correct
24 Correct 32 ms 28636 KB Output is correct
25 Correct 29 ms 28516 KB Output is correct
26 Correct 29 ms 28636 KB Output is correct
27 Correct 28 ms 28644 KB Output is correct
28 Correct 33 ms 28564 KB Output is correct
29 Correct 29 ms 28528 KB Output is correct
30 Correct 30 ms 28552 KB Output is correct
31 Correct 3688 ms 39428 KB Output is correct
32 Correct 151 ms 35184 KB Output is correct
33 Correct 312 ms 36952 KB Output is correct
34 Correct 2144 ms 37048 KB Output is correct
35 Correct 1527 ms 39380 KB Output is correct
36 Correct 363 ms 39276 KB Output is correct
37 Correct 222 ms 36008 KB Output is correct
38 Correct 151 ms 35860 KB Output is correct
39 Correct 118 ms 35620 KB Output is correct
40 Correct 114 ms 35556 KB Output is correct
41 Correct 311 ms 35832 KB Output is correct
42 Correct 412 ms 35576 KB Output is correct
43 Correct 361 ms 39016 KB Output is correct
44 Correct 237 ms 35832 KB Output is correct
45 Correct 161 ms 35736 KB Output is correct
46 Correct 107 ms 35612 KB Output is correct
47 Correct 102 ms 35268 KB Output is correct
48 Correct 96 ms 35252 KB Output is correct
49 Correct 111 ms 35448 KB Output is correct
50 Correct 261 ms 35516 KB Output is correct
51 Correct 98 ms 35448 KB Output is correct
52 Correct 1533 ms 83240 KB Output is correct
53 Correct 1923 ms 85724 KB Output is correct
54 Correct 644 ms 67960 KB Output is correct
55 Correct 1297 ms 80452 KB Output is correct
56 Correct 2021 ms 85136 KB Output is correct
57 Correct 1833 ms 85452 KB Output is correct
58 Correct 420 ms 68140 KB Output is correct
59 Correct 978 ms 80376 KB Output is correct
60 Correct 1201 ms 84728 KB Output is correct
61 Correct 1401 ms 86132 KB Output is correct
62 Correct 1022 ms 84984 KB Output is correct
63 Correct 1274 ms 85968 KB Output is correct
64 Correct 2254 ms 85820 KB Output is correct
65 Correct 769 ms 65756 KB Output is correct
66 Correct 3341 ms 85460 KB Output is correct
67 Correct 603 ms 66164 KB Output is correct
68 Correct 1383 ms 80956 KB Output is correct
69 Correct 1213 ms 78640 KB Output is correct
70 Correct 4366 ms 85652 KB Output is correct
71 Correct 3577 ms 85324 KB Output is correct
72 Correct 620 ms 67204 KB Output is correct
73 Correct 1640 ms 81400 KB Output is correct
74 Correct 2066 ms 84572 KB Output is correct
75 Correct 2705 ms 84976 KB Output is correct
76 Correct 1224 ms 83056 KB Output is correct
77 Correct 1163 ms 82376 KB Output is correct
78 Correct 1574 ms 83352 KB Output is correct
79 Correct 1950 ms 84320 KB Output is correct
80 Correct 1554 ms 83068 KB Output is correct
81 Incorrect 132 ms 40788 KB Output isn't correct
82 Halted 0 ms 0 KB -