oj.uz

Submission #254857

# Submission time Handle Problem Language Result Execution time Memory
254857 2020-07-30T18:16:37 Z amoo_safar New Home (APIO18_new_home) C++11
47 / 100
 5000 ms 482480 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef pair<int, int> pii;

const int N = 3e5 + 10;

int n, q, k;
int x[N], t[N], a[N], b[N];
int y[N], c[N], ans[N];

vector<int> V;


map<int, int> mp[N];
set<int> rec[N];

multiset<int> seg[N << 2];

priority_queue<int, vector<int>, greater<int>> MnA[N << 2], MnR[N << 2];
priority_queue<int> MxA[N << 2], MxR[N << 2];

void Ins(int id, int l, int r, int x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		//seg[id].insert(x);
		MnA[id].push(x);
		MxA[id].push(x);
		return ;
	}
	int mid = (L + R) >> 1;
	Ins(id << 1, l, r, x, L, mid);
	Ins(id << 1 | 1, l, r, x, mid, R);
}
void Rem(int id, int l, int r, int x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		//seg[id].erase(seg[id].find(x));
		MnR[id].push(x);
		MxR[id].push(x);
		return ;
	}
	int mid = (L + R) >> 1;
	Rem(id << 1, l, r, x, L, mid);
	Rem(id << 1 | 1, l, r, x, mid, R);
}

int MN, MX, CNT;
void Get(int id, int idx, int L, int R){
	CNT += MnA[id].size() - MnR[id].size();
	if(MnA[id].size() - MnR[id].size() > 0){
		while(!MnR[id].empty() && MnA[id].top() == MnR[id].top()){
			MnA[id].pop();
			MnR[id].pop();
		}
		while(!MxR[id].empty() && MxA[id].top() == MxR[id].top()){
			MxA[id].pop();
			MxR[id].pop();
		}
		MN = min(MN, MnA[id].top());
		MX = max(MX, MxA[id].top());
	}
	if(R - L == 1) return ;
	int mid = (L + R) >> 1;
	if(idx < mid) Get(id << 1, idx, L, mid);
	else Get(id << 1 | 1, idx, mid, R);
}

template<typename T>
T Prev(T A){return --A; };
template<typename T>
T Next(T A){return ++A; };

inline pii GetRange(pii R){
	return pii(lower_bound(all(V), R.F) - V.begin(), upper_bound(all(V), R.S) - V.begin());
}
inline pii GetRange(int tp, int pl){
	set<int>::iterator it = rec[tp].find(pl);
	int resL, resR;

	if(it == rec[tp].begin()) resL = 1;
	else resL = ( (*Prev(it)) + (*it)) / 2 + 1;

	if(Next(it) == rec[tp].end()) resR = 1e8;
	else resR = ( (*Next(it)) + (*it)) / 2;
	return pii(resL, resR);
}

int SegGet(int pl){
	//cerr << "? " << pl << '\n';
	MN = 1e8 + 1;
	MX = 0;
	CNT = 0;
	Get(1, lower_bound(all(V), pl) - V.begin(), 0, V.size());
	if(CNT != k) return -1;
	return max(MX - pl, pl - MN);
}
void SegRem(int tp, int pl){
	pii ran = GetRange(GetRange(tp, pl));
	Rem(1, ran.F, ran.S, pl, 0, V.size());
}
void SegAdd(int tp, int pl){
	pii ran = GetRange(GetRange(tp, pl));
	Ins(1, ran.F, ran.S, pl, 0, V.size());
}
void Add(int tp, int pl){
	//cerr << "+ " << tp << ' ' << pl << '\n';
	mp[tp][pl] ++;
	if(mp[tp][pl] > 1) return ;

	auto it = rec[tp].lower_bound(pl);
	int nx = -1, la = -1;
	if(it != rec[tp].end()) nx = *it;
	if(it != rec[tp].begin()) la = *Prev(it);
	if(nx != -1) SegRem(tp, nx);
	if(la != -1) SegRem(tp, la);

	rec[tp].insert(pl);
	if(nx != -1) SegAdd(tp, nx);
	if(la != -1) SegAdd(tp, la);
	SegAdd(tp, pl);
}
void Erase(int tp, int pl){
	//cerr << "- " << tp << ' ' << pl << '\n';
	mp[tp][pl] --;
	if(mp[tp][pl] > 0) return ;

	auto it = rec[tp].find(pl);
	int nx = -1, la = -1;
	
	if(Next(it) != rec[tp].end()) nx = *Next(it);
	if(it != rec[tp].begin()) la = *Prev(it);
	
	if(nx != -1) SegRem(tp, nx);
	if(la != -1) SegRem(tp, la);
	SegRem(tp, pl);

	rec[tp].erase(pl);
	
	if(nx != -1) SegAdd(tp, nx);
	if(la != -1) SegAdd(tp, la);
}

vector<int> Ea[N], Er[N], Eq[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> t[i] >> a[i] >> b[i];
		b[i] ++;
		V.pb(a[i]); V.pb(b[i]);
	}
	for(int i = 1; i <= q; i++){
		cin >> y[i] >> c[i];
	}

	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	int AllT = V.size();
	for(int i = 1; i <= n; i++){
		a[i] = lower_bound(all(V), a[i]) - V.begin();
		b[i] = lower_bound(all(V), b[i]) - V.begin();
		Ea[a[i]].pb(i);
		Er[b[i]].pb(i);
		//cerr << "!!! " << a[i] << ' ' << b[i] << '\n';
	}
	for(int i = 1; i <= q; i++){
		if(c[i] < V[0]){
			ans[i] = -1;
			continue;
		}
		c[i] = (upper_bound(all(V), c[i]) - V.begin() ) - 1;
		Eq[c[i]].pb(i);
		//cerr << "? " << c[i] << '\n';
	}

	V.clear();
	//for(int i = 1; i <= n; i++) V.pb(x[i]);
	for(int i = 1; i <= q; i++) V.pb(y[i]);
	sort(all(V)); V.resize(unique(all(V)) - V.begin());

	for(int tm = 0; tm < AllT; tm++){
		for(auto i : Er[tm])
			Erase(t[i], x[i]);
		for(auto i : Ea[tm])
			Add(t[i], x[i]);
		for(auto i : Eq[tm])
			ans[i] = SegGet(y[i]);
		//cerr << '\n';
	}
	for(int i = 1; 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 256376 KB Output is correct
2 Correct 165 ms 256376 KB Output is correct
3 Correct 165 ms 256376 KB Output is correct
4 Correct 160 ms 256376 KB Output is correct
5 Correct 155 ms 256376 KB Output is correct
6 Correct 158 ms 256632 KB Output is correct
7 Correct 162 ms 256632 KB Output is correct
8 Correct 170 ms 256504 KB Output is correct
9 Correct 167 ms 256504 KB Output is correct
10 Correct 151 ms 256628 KB Output is correct
11 Correct 154 ms 256504 KB Output is correct
12 Correct 151 ms 256632 KB Output is correct
13 Correct 156 ms 256504 KB Output is correct
14 Correct 147 ms 256504 KB Output is correct
15 Correct 138 ms 256504 KB Output is correct
16 Correct 136 ms 256504 KB Output is correct
17 Correct 137 ms 256632 KB Output is correct
18 Correct 138 ms 256632 KB Output is correct
19 Correct 137 ms 256504 KB Output is correct
20 Correct 138 ms 256504 KB Output is correct
21 Correct 138 ms 256408 KB Output is correct
22 Correct 139 ms 256504 KB Output is correct
23 Correct 140 ms 256504 KB Output is correct
24 Correct 143 ms 256504 KB Output is correct
25 Correct 137 ms 256632 KB Output is correct
26 Correct 142 ms 256632 KB Output is correct
27 Correct 137 ms 256504 KB Output is correct
28 Correct 136 ms 256488 KB Output is correct
29 Correct 138 ms 256632 KB Output is correct
30 Correct 153 ms 256504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 256376 KB Output is correct
2 Correct 165 ms 256376 KB Output is correct
3 Correct 165 ms 256376 KB Output is correct
4 Correct 160 ms 256376 KB Output is correct
5 Correct 155 ms 256376 KB Output is correct
6 Correct 158 ms 256632 KB Output is correct
7 Correct 162 ms 256632 KB Output is correct
8 Correct 170 ms 256504 KB Output is correct
9 Correct 167 ms 256504 KB Output is correct
10 Correct 151 ms 256628 KB Output is correct
11 Correct 154 ms 256504 KB Output is correct
12 Correct 151 ms 256632 KB Output is correct
13 Correct 156 ms 256504 KB Output is correct
14 Correct 147 ms 256504 KB Output is correct
15 Correct 138 ms 256504 KB Output is correct
16 Correct 136 ms 256504 KB Output is correct
17 Correct 137 ms 256632 KB Output is correct
18 Correct 138 ms 256632 KB Output is correct
19 Correct 137 ms 256504 KB Output is correct
20 Correct 138 ms 256504 KB Output is correct
21 Correct 138 ms 256408 KB Output is correct
22 Correct 139 ms 256504 KB Output is correct
23 Correct 140 ms 256504 KB Output is correct
24 Correct 143 ms 256504 KB Output is correct
25 Correct 137 ms 256632 KB Output is correct
26 Correct 142 ms 256632 KB Output is correct
27 Correct 137 ms 256504 KB Output is correct
28 Correct 136 ms 256488 KB Output is correct
29 Correct 138 ms 256632 KB Output is correct
30 Correct 153 ms 256504 KB Output is correct
31 Correct 2908 ms 332376 KB Output is correct
32 Correct 194 ms 260464 KB Output is correct
33 Correct 2173 ms 306400 KB Output is correct
34 Correct 3195 ms 332372 KB Output is correct
35 Correct 3062 ms 324216 KB Output is correct
36 Correct 1927 ms 304812 KB Output is correct
37 Correct 1569 ms 309496 KB Output is correct
38 Correct 1355 ms 297076 KB Output is correct
39 Correct 975 ms 299096 KB Output is correct
40 Correct 996 ms 296420 KB Output is correct
41 Correct 1455 ms 295288 KB Output is correct
42 Correct 1491 ms 296132 KB Output is correct
43 Correct 207 ms 262388 KB Output is correct
44 Correct 1410 ms 295156 KB Output is correct
45 Correct 1378 ms 293492 KB Output is correct
46 Correct 1277 ms 294568 KB Output is correct
47 Correct 624 ms 291828 KB Output is correct
48 Correct 650 ms 292720 KB Output is correct
49 Correct 785 ms 294516 KB Output is correct
50 Correct 816 ms 296436 KB Output is correct
51 Correct 840 ms 294004 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5070 ms 465712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 482480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 256376 KB Output is correct
2 Correct 165 ms 256376 KB Output is correct
3 Correct 165 ms 256376 KB Output is correct
4 Correct 160 ms 256376 KB Output is correct
5 Correct 155 ms 256376 KB Output is correct
6 Correct 158 ms 256632 KB Output is correct
7 Correct 162 ms 256632 KB Output is correct
8 Correct 170 ms 256504 KB Output is correct
9 Correct 167 ms 256504 KB Output is correct
10 Correct 151 ms 256628 KB Output is correct
11 Correct 154 ms 256504 KB Output is correct
12 Correct 151 ms 256632 KB Output is correct
13 Correct 156 ms 256504 KB Output is correct
14 Correct 147 ms 256504 KB Output is correct
15 Correct 138 ms 256504 KB Output is correct
16 Correct 136 ms 256504 KB Output is correct
17 Correct 137 ms 256632 KB Output is correct
18 Correct 138 ms 256632 KB Output is correct
19 Correct 137 ms 256504 KB Output is correct
20 Correct 138 ms 256504 KB Output is correct
21 Correct 138 ms 256408 KB Output is correct
22 Correct 139 ms 256504 KB Output is correct
23 Correct 140 ms 256504 KB Output is correct
24 Correct 143 ms 256504 KB Output is correct
25 Correct 137 ms 256632 KB Output is correct
26 Correct 142 ms 256632 KB Output is correct
27 Correct 137 ms 256504 KB Output is correct
28 Correct 136 ms 256488 KB Output is correct
29 Correct 138 ms 256632 KB Output is correct
30 Correct 153 ms 256504 KB Output is correct
31 Correct 2908 ms 332376 KB Output is correct
32 Correct 194 ms 260464 KB Output is correct
33 Correct 2173 ms 306400 KB Output is correct
34 Correct 3195 ms 332372 KB Output is correct
35 Correct 3062 ms 324216 KB Output is correct
36 Correct 1927 ms 304812 KB Output is correct
37 Correct 1569 ms 309496 KB Output is correct
38 Correct 1355 ms 297076 KB Output is correct
39 Correct 975 ms 299096 KB Output is correct
40 Correct 996 ms 296420 KB Output is correct
41 Correct 1455 ms 295288 KB Output is correct
42 Correct 1491 ms 296132 KB Output is correct
43 Correct 207 ms 262388 KB Output is correct
44 Correct 1410 ms 295156 KB Output is correct
45 Correct 1378 ms 293492 KB Output is correct
46 Correct 1277 ms 294568 KB Output is correct
47 Correct 624 ms 291828 KB Output is correct
48 Correct 650 ms 292720 KB Output is correct
49 Correct 785 ms 294516 KB Output is correct
50 Correct 816 ms 296436 KB Output is correct
51 Correct 840 ms 294004 KB Output is correct
52 Correct 436 ms 273652 KB Output is correct
53 Correct 375 ms 271044 KB Output is correct
54 Correct 1214 ms 301556 KB Output is correct
55 Correct 1028 ms 289908 KB Output is correct
56 Correct 847 ms 286708 KB Output is correct
57 Correct 1264 ms 293364 KB Output is correct
58 Correct 1065 ms 289580 KB Output is correct
59 Correct 887 ms 285940 KB Output is correct
60 Correct 1407 ms 293864 KB Output is correct
61 Correct 218 ms 269172 KB Output is correct
62 Correct 407 ms 273664 KB Output is correct
63 Correct 788 ms 288668 KB Output is correct
64 Correct 1020 ms 294388 KB Output is correct
65 Correct 1273 ms 300288 KB Output is correct
66 Correct 1482 ms 297208 KB Output is correct
67 Correct 364 ms 273140 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 256376 KB Output is correct
2 Correct 165 ms 256376 KB Output is correct
3 Correct 165 ms 256376 KB Output is correct
4 Correct 160 ms 256376 KB Output is correct
5 Correct 155 ms 256376 KB Output is correct
6 Correct 158 ms 256632 KB Output is correct
7 Correct 162 ms 256632 KB Output is correct
8 Correct 170 ms 256504 KB Output is correct
9 Correct 167 ms 256504 KB Output is correct
10 Correct 151 ms 256628 KB Output is correct
11 Correct 154 ms 256504 KB Output is correct
12 Correct 151 ms 256632 KB Output is correct
13 Correct 156 ms 256504 KB Output is correct
14 Correct 147 ms 256504 KB Output is correct
15 Correct 138 ms 256504 KB Output is correct
16 Correct 136 ms 256504 KB Output is correct
17 Correct 137 ms 256632 KB Output is correct
18 Correct 138 ms 256632 KB Output is correct
19 Correct 137 ms 256504 KB Output is correct
20 Correct 138 ms 256504 KB Output is correct
21 Correct 138 ms 256408 KB Output is correct
22 Correct 139 ms 256504 KB Output is correct
23 Correct 140 ms 256504 KB Output is correct
24 Correct 143 ms 256504 KB Output is correct
25 Correct 137 ms 256632 KB Output is correct
26 Correct 142 ms 256632 KB Output is correct
27 Correct 137 ms 256504 KB Output is correct
28 Correct 136 ms 256488 KB Output is correct
29 Correct 138 ms 256632 KB Output is correct
30 Correct 153 ms 256504 KB Output is correct
31 Correct 2908 ms 332376 KB Output is correct
32 Correct 194 ms 260464 KB Output is correct
33 Correct 2173 ms 306400 KB Output is correct
34 Correct 3195 ms 332372 KB Output is correct
35 Correct 3062 ms 324216 KB Output is correct
36 Correct 1927 ms 304812 KB Output is correct
37 Correct 1569 ms 309496 KB Output is correct
38 Correct 1355 ms 297076 KB Output is correct
39 Correct 975 ms 299096 KB Output is correct
40 Correct 996 ms 296420 KB Output is correct
41 Correct 1455 ms 295288 KB Output is correct
42 Correct 1491 ms 296132 KB Output is correct
43 Correct 207 ms 262388 KB Output is correct
44 Correct 1410 ms 295156 KB Output is correct
45 Correct 1378 ms 293492 KB Output is correct
46 Correct 1277 ms 294568 KB Output is correct
47 Correct 624 ms 291828 KB Output is correct
48 Correct 650 ms 292720 KB Output is correct
49 Correct 785 ms 294516 KB Output is correct
50 Correct 816 ms 296436 KB Output is correct
51 Correct 840 ms 294004 KB Output is correct
52 Execution timed out 5070 ms 465712 KB Time limit exceeded
53 Halted 0 ms 0 KB -