답안 #254825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254825	2020-07-30T17:11:31 Z	amoo_safar	새 집 (APIO18_new_home)	C++17	47 / 100	5000 ms	281724 KB

new_home

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#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 string str;
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];

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);
		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));
		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 += seg[id].size();
	if(!seg[id].empty()){
		MN = min(MN, *seg[id].begin());
		MX = max(MX, *seg[id].rbegin());
	}
	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; };

pii GetRange(pii R){
	return pii(lower_bound(all(V), R.F) - V.begin(), upper_bound(all(V), R.S) - V.begin());
}
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 : Ea[tm])
			Add(t[i], x[i]);
		for(auto i : Er[tm])
			Erase(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;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	106104 KB	Output is correct
2	Correct	59 ms	106072 KB	Output is correct
3	Correct	57 ms	106104 KB	Output is correct
4	Correct	57 ms	106104 KB	Output is correct
5	Correct	61 ms	106104 KB	Output is correct
6	Correct	65 ms	106232 KB	Output is correct
7	Correct	55 ms	106232 KB	Output is correct
8	Correct	63 ms	106360 KB	Output is correct
9	Correct	59 ms	106244 KB	Output is correct
10	Correct	67 ms	106232 KB	Output is correct
11	Correct	68 ms	106104 KB	Output is correct
12	Correct	66 ms	106104 KB	Output is correct
13	Correct	88 ms	106104 KB	Output is correct
14	Correct	85 ms	106104 KB	Output is correct
15	Correct	59 ms	106232 KB	Output is correct
16	Correct	57 ms	106232 KB	Output is correct
17	Correct	61 ms	106232 KB	Output is correct
18	Correct	62 ms	106232 KB	Output is correct
19	Correct	60 ms	106232 KB	Output is correct
20	Correct	58 ms	106240 KB	Output is correct
21	Correct	56 ms	106232 KB	Output is correct
22	Correct	57 ms	106236 KB	Output is correct
23	Correct	56 ms	106236 KB	Output is correct
24	Correct	58 ms	106232 KB	Output is correct
25	Correct	68 ms	106232 KB	Output is correct
26	Correct	58 ms	106104 KB	Output is correct
27	Correct	57 ms	106104 KB	Output is correct
28	Correct	63 ms	106104 KB	Output is correct
29	Correct	60 ms	106212 KB	Output is correct
30	Correct	56 ms	106104 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	106104 KB	Output is correct
2	Correct	59 ms	106072 KB	Output is correct
3	Correct	57 ms	106104 KB	Output is correct
4	Correct	57 ms	106104 KB	Output is correct
5	Correct	61 ms	106104 KB	Output is correct
6	Correct	65 ms	106232 KB	Output is correct
7	Correct	55 ms	106232 KB	Output is correct
8	Correct	63 ms	106360 KB	Output is correct
9	Correct	59 ms	106244 KB	Output is correct
10	Correct	67 ms	106232 KB	Output is correct
11	Correct	68 ms	106104 KB	Output is correct
12	Correct	66 ms	106104 KB	Output is correct
13	Correct	88 ms	106104 KB	Output is correct
14	Correct	85 ms	106104 KB	Output is correct
15	Correct	59 ms	106232 KB	Output is correct
16	Correct	57 ms	106232 KB	Output is correct
17	Correct	61 ms	106232 KB	Output is correct
18	Correct	62 ms	106232 KB	Output is correct
19	Correct	60 ms	106232 KB	Output is correct
20	Correct	58 ms	106240 KB	Output is correct
21	Correct	56 ms	106232 KB	Output is correct
22	Correct	57 ms	106236 KB	Output is correct
23	Correct	56 ms	106236 KB	Output is correct
24	Correct	58 ms	106232 KB	Output is correct
25	Correct	68 ms	106232 KB	Output is correct
26	Correct	58 ms	106104 KB	Output is correct
27	Correct	57 ms	106104 KB	Output is correct
28	Correct	63 ms	106104 KB	Output is correct
29	Correct	60 ms	106212 KB	Output is correct
30	Correct	56 ms	106104 KB	Output is correct
31	Correct	2827 ms	145416 KB	Output is correct
32	Correct	107 ms	110196 KB	Output is correct
33	Correct	1244 ms	124148 KB	Output is correct
34	Correct	2785 ms	129388 KB	Output is correct
35	Correct	2306 ms	140980 KB	Output is correct
36	Correct	1266 ms	131116 KB	Output is correct
37	Correct	911 ms	120560 KB	Output is correct
38	Correct	713 ms	119784 KB	Output is correct
39	Correct	649 ms	119340 KB	Output is correct
40	Correct	641 ms	119284 KB	Output is correct
41	Correct	688 ms	119668 KB	Output is correct
42	Correct	732 ms	119604 KB	Output is correct
43	Correct	119 ms	112116 KB	Output is correct
44	Correct	700 ms	119660 KB	Output is correct
45	Correct	594 ms	119456 KB	Output is correct
46	Correct	526 ms	119456 KB	Output is correct
47	Correct	376 ms	118768 KB	Output is correct
48	Correct	366 ms	118644 KB	Output is correct
49	Correct	481 ms	118900 KB	Output is correct
50	Correct	573 ms	119284 KB	Output is correct
51	Correct	465 ms	118988 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5100 ms	281724 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5105 ms	237664 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	106104 KB	Output is correct
2	Correct	59 ms	106072 KB	Output is correct
3	Correct	57 ms	106104 KB	Output is correct
4	Correct	57 ms	106104 KB	Output is correct
5	Correct	61 ms	106104 KB	Output is correct
6	Correct	65 ms	106232 KB	Output is correct
7	Correct	55 ms	106232 KB	Output is correct
8	Correct	63 ms	106360 KB	Output is correct
9	Correct	59 ms	106244 KB	Output is correct
10	Correct	67 ms	106232 KB	Output is correct
11	Correct	68 ms	106104 KB	Output is correct
12	Correct	66 ms	106104 KB	Output is correct
13	Correct	88 ms	106104 KB	Output is correct
14	Correct	85 ms	106104 KB	Output is correct
15	Correct	59 ms	106232 KB	Output is correct
16	Correct	57 ms	106232 KB	Output is correct
17	Correct	61 ms	106232 KB	Output is correct
18	Correct	62 ms	106232 KB	Output is correct
19	Correct	60 ms	106232 KB	Output is correct
20	Correct	58 ms	106240 KB	Output is correct
21	Correct	56 ms	106232 KB	Output is correct
22	Correct	57 ms	106236 KB	Output is correct
23	Correct	56 ms	106236 KB	Output is correct
24	Correct	58 ms	106232 KB	Output is correct
25	Correct	68 ms	106232 KB	Output is correct
26	Correct	58 ms	106104 KB	Output is correct
27	Correct	57 ms	106104 KB	Output is correct
28	Correct	63 ms	106104 KB	Output is correct
29	Correct	60 ms	106212 KB	Output is correct
30	Correct	56 ms	106104 KB	Output is correct
31	Correct	2827 ms	145416 KB	Output is correct
32	Correct	107 ms	110196 KB	Output is correct
33	Correct	1244 ms	124148 KB	Output is correct
34	Correct	2785 ms	129388 KB	Output is correct
35	Correct	2306 ms	140980 KB	Output is correct
36	Correct	1266 ms	131116 KB	Output is correct
37	Correct	911 ms	120560 KB	Output is correct
38	Correct	713 ms	119784 KB	Output is correct
39	Correct	649 ms	119340 KB	Output is correct
40	Correct	641 ms	119284 KB	Output is correct
41	Correct	688 ms	119668 KB	Output is correct
42	Correct	732 ms	119604 KB	Output is correct
43	Correct	119 ms	112116 KB	Output is correct
44	Correct	700 ms	119660 KB	Output is correct
45	Correct	594 ms	119456 KB	Output is correct
46	Correct	526 ms	119456 KB	Output is correct
47	Correct	376 ms	118768 KB	Output is correct
48	Correct	366 ms	118644 KB	Output is correct
49	Correct	481 ms	118900 KB	Output is correct
50	Correct	573 ms	119284 KB	Output is correct
51	Correct	465 ms	118988 KB	Output is correct
52	Correct	354 ms	124984 KB	Output is correct
53	Correct	322 ms	120436 KB	Output is correct
54	Correct	1661 ms	148620 KB	Output is correct
55	Correct	582 ms	121564 KB	Output is correct
56	Correct	504 ms	122228 KB	Output is correct
57	Correct	694 ms	120436 KB	Output is correct
58	Correct	633 ms	121332 KB	Output is correct
59	Correct	561 ms	122100 KB	Output is correct
60	Correct	677 ms	119924 KB	Output is correct
61	Correct	140 ms	120396 KB	Output is correct
62	Correct	321 ms	124788 KB	Output is correct
63	Correct	884 ms	136816 KB	Output is correct
64	Correct	1153 ms	135540 KB	Output is correct
65	Correct	1194 ms	124804 KB	Output is correct
66	Correct	849 ms	120092 KB	Output is correct
67	Correct	551 ms	115576 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	106104 KB	Output is correct
2	Correct	59 ms	106072 KB	Output is correct
3	Correct	57 ms	106104 KB	Output is correct
4	Correct	57 ms	106104 KB	Output is correct
5	Correct	61 ms	106104 KB	Output is correct
6	Correct	65 ms	106232 KB	Output is correct
7	Correct	55 ms	106232 KB	Output is correct
8	Correct	63 ms	106360 KB	Output is correct
9	Correct	59 ms	106244 KB	Output is correct
10	Correct	67 ms	106232 KB	Output is correct
11	Correct	68 ms	106104 KB	Output is correct
12	Correct	66 ms	106104 KB	Output is correct
13	Correct	88 ms	106104 KB	Output is correct
14	Correct	85 ms	106104 KB	Output is correct
15	Correct	59 ms	106232 KB	Output is correct
16	Correct	57 ms	106232 KB	Output is correct
17	Correct	61 ms	106232 KB	Output is correct
18	Correct	62 ms	106232 KB	Output is correct
19	Correct	60 ms	106232 KB	Output is correct
20	Correct	58 ms	106240 KB	Output is correct
21	Correct	56 ms	106232 KB	Output is correct
22	Correct	57 ms	106236 KB	Output is correct
23	Correct	56 ms	106236 KB	Output is correct
24	Correct	58 ms	106232 KB	Output is correct
25	Correct	68 ms	106232 KB	Output is correct
26	Correct	58 ms	106104 KB	Output is correct
27	Correct	57 ms	106104 KB	Output is correct
28	Correct	63 ms	106104 KB	Output is correct
29	Correct	60 ms	106212 KB	Output is correct
30	Correct	56 ms	106104 KB	Output is correct
31	Correct	2827 ms	145416 KB	Output is correct
32	Correct	107 ms	110196 KB	Output is correct
33	Correct	1244 ms	124148 KB	Output is correct
34	Correct	2785 ms	129388 KB	Output is correct
35	Correct	2306 ms	140980 KB	Output is correct
36	Correct	1266 ms	131116 KB	Output is correct
37	Correct	911 ms	120560 KB	Output is correct
38	Correct	713 ms	119784 KB	Output is correct
39	Correct	649 ms	119340 KB	Output is correct
40	Correct	641 ms	119284 KB	Output is correct
41	Correct	688 ms	119668 KB	Output is correct
42	Correct	732 ms	119604 KB	Output is correct
43	Correct	119 ms	112116 KB	Output is correct
44	Correct	700 ms	119660 KB	Output is correct
45	Correct	594 ms	119456 KB	Output is correct
46	Correct	526 ms	119456 KB	Output is correct
47	Correct	376 ms	118768 KB	Output is correct
48	Correct	366 ms	118644 KB	Output is correct
49	Correct	481 ms	118900 KB	Output is correct
50	Correct	573 ms	119284 KB	Output is correct
51	Correct	465 ms	118988 KB	Output is correct
52	Execution timed out	5100 ms	281724 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #254825

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0