답안 #255048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255048	2020-07-31T06:56:38 Z	amoo_safar	새 집 (APIO18_new_home)	C++14	47 / 100	5000 ms	162512 KB

new_home

// 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;
const int Inf = 1e9;

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

unordered_map<int, int> mp[N];
set<int> rec[N];
 
const int SGN = (1 << 19);
int seg[SGN << 1];
/*
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);
}
*/
void Set(int idx, int v){
	idx += SGN;
	seg[idx] = v;
	while(idx >>= 1){
		seg[idx] = min(seg[idx << 1], seg[idx << 1 | 1]);
	}
	/*if(R - L == 1){
		seg[id] = v;
		return ;
	}
	int mid = (L + R) >> 1;
	if(idx < mid) Set(id << 1, idx, v, L, mid);
	else Set(id << 1 | 1, idx, v, mid, R);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	*/
}
 

int MN;
/*
int Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return Inf;
	if(l <= L && R <= r) return seg[id];
	
	int mid = (L + R) >> 1;
	return min(Get(id << 1, l, r, L, mid), Get(id << 1 | 1, l, r, mid, R));
	//if(idx < mid) Get(id << 1, idx, L, mid);
	//else Get(id << 1 | 1, idx, mid, R);
}
*/

int Get(int l){
	l += SGN;
	int r = SGN + SGN;
	int res = Inf;
	while(l != r){
		if(l & 1)
			res = min(res, seg[l ++]);
		l >>= 1; r >>= 1;
	}
	return res;
}
template<typename T>
T Prev(T A){return --A; };
template<typename T>
T Next(T A){return ++A; };
 
pii GetRange(pii R){
	return pii(R.F, upper_bound(all(V), R.S) - V.begin());
}
pii GetRange(int tp, int pl){
	set<int>::iterator it = rec[tp].find(pl);
	int resL = pl, 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);
}
 
void SegGet(int qn){
	//cerr << "? " << pl << '\n';
	int pl = y[qn];
	//MN = Get(1, (lower_bound(all(V), pl) - V.begin()), V.size(), 0, SGN);
	MN = Get( lower_bound(all(V), pl) - V.begin() );
	//cerr << qn << ' ' << MN << '\n';
	ans[qn] = max(ans[qn], pl - MN);
	//if(CNT != k) return -1;
	//return max(MX - pl, pl - MN);
}
priority_queue<int, vector<int>, greater<int> > ms[N], msR[N];

inline void Norm(int idx){
	while(!msR[idx].empty() && ms[idx].top() == msR[idx].top()){
		msR[idx].pop();
		ms[idx].pop();
	}
}
//multiset<int> ms[N];
inline void SegRem(int tp, int pl){
	pii ran = GetRange(GetRange(tp, pl));
	
	if(ran.S == 0) return ;
	ran.S --;
	msR[ran.S].push(ran.F);
	Norm(ran.S);
	//ms[ran.S - 1].erase(ms[ran.S - 1].find(ran.F));
	Set(ran.S, (ms[ran.S].empty() ? Inf : ms[ran.S].top()));
	//Rem(1, ran.F, ran.S, pl, 0, V.size());
}
inline void SegAdd(int tp, int pl){
	pii ran = GetRange(GetRange(tp, pl));
	if(ran.S == 0) return ;
	ran.S --;

	ms[ran.S].push(ran.F);
	Norm(ran.S);
	//debug(ran.S - 1);
	Set(ran.S, ms[ran.S].top());
	//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 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 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 flg[N], open[N], cntn;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("Big.txt", "r", stdin);
	//freopen("Out.txt", "w", stdout);

	//clock_t StartTime = clock();

	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];
		V.pb(c[i]);
	}
 
	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	V.pb(1e8 + 1);
	int AllT = V.size();
	assert(AllT < N);
	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++){
		c[i] = (lower_bound(all(V), c[i]) - V.begin() );
		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());
 
	memset(seg, 31, sizeof seg);

	for(int tm = 0; tm < AllT; tm++){
		for(auto i : Ea[tm]){
			Add(t[i], x[i]);
			open[t[i]] ++;
			if(open[t[i]] == 1) cntn ++;
		}
		for(auto i : Er[tm]){
			Erase(t[i], x[i]);
			open[t[i]] --;
			if(open[t[i]] == 0) cntn --;
		}
		for(auto i : Eq[tm]){
			SegGet(i);
			//cerr << i << ' ' << c
			if(cntn < k) flg[i] = true;
		}
		//cerr << '\n';
	}
	
	int SM = 100000001;
	for(int i = 1; i <= n; i ++) x[i] = SM - x[i];
	for(int i = 1; i <= q; i ++) y[i] = SM - y[i];
	for(auto &el : V)
		if(el < SM)
			el = SM - el;
	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	
	memset(seg, 31, sizeof seg);	
	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])
			SegGet(i);
		//cerr << '\n';
	}
 	


	for(int i = 1; i <= q; i++) cout << (flg[i] ? -1 : ans[i]) << '\n';
	

	//cerr << fixed << setprecision(4) << (double)(clock() - StartTime)/CLOCKS_PER_SEC << '\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

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	74880 KB	Output is correct
2	Correct	47 ms	75000 KB	Output is correct
3	Correct	45 ms	74872 KB	Output is correct
4	Correct	46 ms	74880 KB	Output is correct
5	Correct	46 ms	75000 KB	Output is correct
6	Correct	46 ms	75000 KB	Output is correct
7	Correct	46 ms	75000 KB	Output is correct
8	Correct	48 ms	75100 KB	Output is correct
9	Correct	54 ms	75000 KB	Output is correct
10	Correct	52 ms	75000 KB	Output is correct
11	Correct	48 ms	75008 KB	Output is correct
12	Correct	47 ms	75136 KB	Output is correct
13	Correct	45 ms	75000 KB	Output is correct
14	Correct	48 ms	75140 KB	Output is correct
15	Correct	46 ms	75000 KB	Output is correct
16	Correct	47 ms	75000 KB	Output is correct
17	Correct	47 ms	75000 KB	Output is correct
18	Correct	45 ms	75000 KB	Output is correct
19	Correct	53 ms	75000 KB	Output is correct
20	Correct	51 ms	75000 KB	Output is correct
21	Correct	46 ms	75000 KB	Output is correct
22	Correct	47 ms	75000 KB	Output is correct
23	Correct	46 ms	75000 KB	Output is correct
24	Correct	47 ms	75000 KB	Output is correct
25	Correct	47 ms	75000 KB	Output is correct
26	Correct	48 ms	75004 KB	Output is correct
27	Correct	45 ms	75000 KB	Output is correct
28	Correct	56 ms	75128 KB	Output is correct
29	Correct	46 ms	75000 KB	Output is correct
30	Correct	45 ms	75000 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	74880 KB	Output is correct
2	Correct	47 ms	75000 KB	Output is correct
3	Correct	45 ms	74872 KB	Output is correct
4	Correct	46 ms	74880 KB	Output is correct
5	Correct	46 ms	75000 KB	Output is correct
6	Correct	46 ms	75000 KB	Output is correct
7	Correct	46 ms	75000 KB	Output is correct
8	Correct	48 ms	75100 KB	Output is correct
9	Correct	54 ms	75000 KB	Output is correct
10	Correct	52 ms	75000 KB	Output is correct
11	Correct	48 ms	75008 KB	Output is correct
12	Correct	47 ms	75136 KB	Output is correct
13	Correct	45 ms	75000 KB	Output is correct
14	Correct	48 ms	75140 KB	Output is correct
15	Correct	46 ms	75000 KB	Output is correct
16	Correct	47 ms	75000 KB	Output is correct
17	Correct	47 ms	75000 KB	Output is correct
18	Correct	45 ms	75000 KB	Output is correct
19	Correct	53 ms	75000 KB	Output is correct
20	Correct	51 ms	75000 KB	Output is correct
21	Correct	46 ms	75000 KB	Output is correct
22	Correct	47 ms	75000 KB	Output is correct
23	Correct	46 ms	75000 KB	Output is correct
24	Correct	47 ms	75000 KB	Output is correct
25	Correct	47 ms	75000 KB	Output is correct
26	Correct	48 ms	75004 KB	Output is correct
27	Correct	45 ms	75000 KB	Output is correct
28	Correct	56 ms	75128 KB	Output is correct
29	Correct	46 ms	75000 KB	Output is correct
30	Correct	45 ms	75000 KB	Output is correct
31	Correct	844 ms	93176 KB	Output is correct
32	Correct	104 ms	78076 KB	Output is correct
33	Correct	823 ms	90780 KB	Output is correct
34	Correct	752 ms	91128 KB	Output is correct
35	Correct	879 ms	93628 KB	Output is correct
36	Correct	888 ms	92920 KB	Output is correct
37	Correct	570 ms	90264 KB	Output is correct
38	Correct	603 ms	90632 KB	Output is correct
39	Correct	456 ms	90096 KB	Output is correct
40	Correct	480 ms	90120 KB	Output is correct
41	Correct	584 ms	89968 KB	Output is correct
42	Correct	507 ms	89840 KB	Output is correct
43	Correct	104 ms	78580 KB	Output is correct
44	Correct	470 ms	90216 KB	Output is correct
45	Correct	462 ms	89964 KB	Output is correct
46	Correct	430 ms	89768 KB	Output is correct
47	Correct	296 ms	88568 KB	Output is correct
48	Correct	287 ms	88696 KB	Output is correct
49	Correct	345 ms	88952 KB	Output is correct
50	Correct	405 ms	89080 KB	Output is correct
51	Correct	386 ms	89208 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3640 ms	159700 KB	Output is correct
2	Execution timed out	5030 ms	159600 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	74880 KB	Output is correct
2	Correct	47 ms	75000 KB	Output is correct
3	Correct	45 ms	74872 KB	Output is correct
4	Correct	46 ms	74880 KB	Output is correct
5	Correct	46 ms	75000 KB	Output is correct
6	Correct	46 ms	75000 KB	Output is correct
7	Correct	46 ms	75000 KB	Output is correct
8	Correct	48 ms	75100 KB	Output is correct
9	Correct	54 ms	75000 KB	Output is correct
10	Correct	52 ms	75000 KB	Output is correct
11	Correct	48 ms	75008 KB	Output is correct
12	Correct	47 ms	75136 KB	Output is correct
13	Correct	45 ms	75000 KB	Output is correct
14	Correct	48 ms	75140 KB	Output is correct
15	Correct	46 ms	75000 KB	Output is correct
16	Correct	47 ms	75000 KB	Output is correct
17	Correct	47 ms	75000 KB	Output is correct
18	Correct	45 ms	75000 KB	Output is correct
19	Correct	53 ms	75000 KB	Output is correct
20	Correct	51 ms	75000 KB	Output is correct
21	Correct	46 ms	75000 KB	Output is correct
22	Correct	47 ms	75000 KB	Output is correct
23	Correct	46 ms	75000 KB	Output is correct
24	Correct	47 ms	75000 KB	Output is correct
25	Correct	47 ms	75000 KB	Output is correct
26	Correct	48 ms	75004 KB	Output is correct
27	Correct	45 ms	75000 KB	Output is correct
28	Correct	56 ms	75128 KB	Output is correct
29	Correct	46 ms	75000 KB	Output is correct
30	Correct	45 ms	75000 KB	Output is correct
31	Correct	844 ms	93176 KB	Output is correct
32	Correct	104 ms	78076 KB	Output is correct
33	Correct	823 ms	90780 KB	Output is correct
34	Correct	752 ms	91128 KB	Output is correct
35	Correct	879 ms	93628 KB	Output is correct
36	Correct	888 ms	92920 KB	Output is correct
37	Correct	570 ms	90264 KB	Output is correct
38	Correct	603 ms	90632 KB	Output is correct
39	Correct	456 ms	90096 KB	Output is correct
40	Correct	480 ms	90120 KB	Output is correct
41	Correct	584 ms	89968 KB	Output is correct
42	Correct	507 ms	89840 KB	Output is correct
43	Correct	104 ms	78580 KB	Output is correct
44	Correct	470 ms	90216 KB	Output is correct
45	Correct	462 ms	89964 KB	Output is correct
46	Correct	430 ms	89768 KB	Output is correct
47	Correct	296 ms	88568 KB	Output is correct
48	Correct	287 ms	88696 KB	Output is correct
49	Correct	345 ms	88952 KB	Output is correct
50	Correct	405 ms	89080 KB	Output is correct
51	Correct	386 ms	89208 KB	Output is correct
52	Correct	367 ms	90484 KB	Output is correct
53	Correct	367 ms	88432 KB	Output is correct
54	Correct	704 ms	92512 KB	Output is correct
55	Correct	418 ms	91132 KB	Output is correct
56	Correct	399 ms	91472 KB	Output is correct
57	Correct	496 ms	90480 KB	Output is correct
58	Correct	484 ms	90872 KB	Output is correct
59	Correct	450 ms	90992 KB	Output is correct
60	Correct	472 ms	90124 KB	Output is correct
61	Correct	154 ms	87796 KB	Output is correct
62	Correct	408 ms	90356 KB	Output is correct
63	Correct	541 ms	91636 KB	Output is correct
64	Correct	511 ms	91636 KB	Output is correct
65	Correct	528 ms	90608 KB	Output is correct
66	Correct	491 ms	90164 KB	Output is correct
67	Correct	313 ms	85620 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	74880 KB	Output is correct
2	Correct	47 ms	75000 KB	Output is correct
3	Correct	45 ms	74872 KB	Output is correct
4	Correct	46 ms	74880 KB	Output is correct
5	Correct	46 ms	75000 KB	Output is correct
6	Correct	46 ms	75000 KB	Output is correct
7	Correct	46 ms	75000 KB	Output is correct
8	Correct	48 ms	75100 KB	Output is correct
9	Correct	54 ms	75000 KB	Output is correct
10	Correct	52 ms	75000 KB	Output is correct
11	Correct	48 ms	75008 KB	Output is correct
12	Correct	47 ms	75136 KB	Output is correct
13	Correct	45 ms	75000 KB	Output is correct
14	Correct	48 ms	75140 KB	Output is correct
15	Correct	46 ms	75000 KB	Output is correct
16	Correct	47 ms	75000 KB	Output is correct
17	Correct	47 ms	75000 KB	Output is correct
18	Correct	45 ms	75000 KB	Output is correct
19	Correct	53 ms	75000 KB	Output is correct
20	Correct	51 ms	75000 KB	Output is correct
21	Correct	46 ms	75000 KB	Output is correct
22	Correct	47 ms	75000 KB	Output is correct
23	Correct	46 ms	75000 KB	Output is correct
24	Correct	47 ms	75000 KB	Output is correct
25	Correct	47 ms	75000 KB	Output is correct
26	Correct	48 ms	75004 KB	Output is correct
27	Correct	45 ms	75000 KB	Output is correct
28	Correct	56 ms	75128 KB	Output is correct
29	Correct	46 ms	75000 KB	Output is correct
30	Correct	45 ms	75000 KB	Output is correct
31	Correct	844 ms	93176 KB	Output is correct
32	Correct	104 ms	78076 KB	Output is correct
33	Correct	823 ms	90780 KB	Output is correct
34	Correct	752 ms	91128 KB	Output is correct
35	Correct	879 ms	93628 KB	Output is correct
36	Correct	888 ms	92920 KB	Output is correct
37	Correct	570 ms	90264 KB	Output is correct
38	Correct	603 ms	90632 KB	Output is correct
39	Correct	456 ms	90096 KB	Output is correct
40	Correct	480 ms	90120 KB	Output is correct
41	Correct	584 ms	89968 KB	Output is correct
42	Correct	507 ms	89840 KB	Output is correct
43	Correct	104 ms	78580 KB	Output is correct
44	Correct	470 ms	90216 KB	Output is correct
45	Correct	462 ms	89964 KB	Output is correct
46	Correct	430 ms	89768 KB	Output is correct
47	Correct	296 ms	88568 KB	Output is correct
48	Correct	287 ms	88696 KB	Output is correct
49	Correct	345 ms	88952 KB	Output is correct
50	Correct	405 ms	89080 KB	Output is correct
51	Correct	386 ms	89208 KB	Output is correct
52	Correct	3640 ms	159700 KB	Output is correct
53	Execution timed out	5030 ms	159600 KB	Time limit exceeded
54	Halted	0 ms	0 KB	-

답안 #255048

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