oj.uz

Submission #255032

# Submission time Handle Problem Language Result Execution time Memory
255032 2020-07-31T04:49:27 Z amoo_safar New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 165016 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;
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;
 
 
map<int, int> mp[N];
set<int> rec[N];
 
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);
}
*/
void Set(int id, int idx, int v, int L, int R){
	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, MX, CNT;
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];
	
	/*CNT += seg[id].size();
	if(!seg[id].empty()){
		MN = min(MN, *seg[id].begin());
		MX = max(MX, *seg[id].rbegin());
	}*/
	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);
}
 
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, V.size());
	//cerr << qn << ' ' << MN << '\n';
	ans[qn] = max(ans[qn], pl - MN);
	//if(CNT != k) return -1;
	//return max(MX - pl, pl - MN);
}
multiset<int> ms[N];
void SegRem(int tp, int pl){
	pii ran = GetRange(GetRange(tp, pl));
	
	if(ran.S == 0) return ;
	ms[ran.S - 1].erase(ms[ran.S - 1].find(ran.F));
	Set(1, ran.S - 1, (ms[ran.S - 1].empty() ? Inf : *ms[ran.S - 1].begin()), 0, V.size());
	//Rem(1, ran.F, ran.S, pl, 0, V.size());
}
void SegAdd(int tp, int pl){
	pii ran = GetRange(GetRange(tp, pl));
	if(ran.S == 0) return ;
	ms[ran.S - 1].insert(ran.F);
	//debug(ran.S - 1);
	Set(1, ran.S - 1, *ms[ran.S - 1].begin(), 0, V.size());
	//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);
	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());
 
	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 <= n; i ++) y[i] = SM - y[i];
	for(auto &x : V)
		if(x < SM)
			x = SM - x;
	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';
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68472 KB Output is correct
2 Correct 40 ms 68472 KB Output is correct
3 Correct 40 ms 68472 KB Output is correct
4 Correct 40 ms 68480 KB Output is correct
5 Correct 40 ms 68472 KB Output is correct
6 Correct 42 ms 68600 KB Output is correct
7 Correct 41 ms 68600 KB Output is correct
8 Correct 42 ms 68604 KB Output is correct
9 Correct 41 ms 68600 KB Output is correct
10 Correct 44 ms 68600 KB Output is correct
11 Correct 44 ms 68608 KB Output is correct
12 Correct 42 ms 68608 KB Output is correct
13 Correct 42 ms 68600 KB Output is correct
14 Correct 43 ms 68636 KB Output is correct
15 Incorrect 42 ms 68600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68472 KB Output is correct
2 Correct 40 ms 68472 KB Output is correct
3 Correct 40 ms 68472 KB Output is correct
4 Correct 40 ms 68480 KB Output is correct
5 Correct 40 ms 68472 KB Output is correct
6 Correct 42 ms 68600 KB Output is correct
7 Correct 41 ms 68600 KB Output is correct
8 Correct 42 ms 68604 KB Output is correct
9 Correct 41 ms 68600 KB Output is correct
10 Correct 44 ms 68600 KB Output is correct
11 Correct 44 ms 68608 KB Output is correct
12 Correct 42 ms 68608 KB Output is correct
13 Correct 42 ms 68600 KB Output is correct
14 Correct 43 ms 68636 KB Output is correct
15 Incorrect 42 ms 68600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4381 ms 156384 KB Output is correct
2 Execution timed out 5104 ms 152464 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68472 KB Output is correct
2 Correct 40 ms 68472 KB Output is correct
3 Correct 40 ms 68472 KB Output is correct
4 Correct 40 ms 68480 KB Output is correct
5 Correct 40 ms 68472 KB Output is correct
6 Correct 42 ms 68600 KB Output is correct
7 Correct 41 ms 68600 KB Output is correct
8 Correct 42 ms 68604 KB Output is correct
9 Correct 41 ms 68600 KB Output is correct
10 Correct 44 ms 68600 KB Output is correct
11 Correct 44 ms 68608 KB Output is correct
12 Correct 42 ms 68608 KB Output is correct
13 Correct 42 ms 68600 KB Output is correct
14 Correct 43 ms 68636 KB Output is correct
15 Incorrect 42 ms 68600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68472 KB Output is correct
2 Correct 40 ms 68472 KB Output is correct
3 Correct 40 ms 68472 KB Output is correct
4 Correct 40 ms 68480 KB Output is correct
5 Correct 40 ms 68472 KB Output is correct
6 Correct 42 ms 68600 KB Output is correct
7 Correct 41 ms 68600 KB Output is correct
8 Correct 42 ms 68604 KB Output is correct
9 Correct 41 ms 68600 KB Output is correct
10 Correct 44 ms 68600 KB Output is correct
11 Correct 44 ms 68608 KB Output is correct
12 Correct 42 ms 68608 KB Output is correct
13 Correct 42 ms 68600 KB Output is correct
14 Correct 43 ms 68636 KB Output is correct
15 Incorrect 42 ms 68600 KB Output isn't correct
16 Halted 0 ms 0 KB -