oj.uz

Submission #393293

# Submission time Handle Problem Language Result Execution time Memory
393293 2021-04-23T06:52:07 Z Nima_Naderi New Home (APIO18_new_home) C++14
0 / 100
 2723 ms 142680 KB 
//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e5 + 10;
const ll MXM = 6e5 + 10;
ll n, k, q, typ;
ll Xs[MXN], Ts[MXN], Ls[MXN], Rs[MXN];
ll Ans[MXN], Fen[2][MXN];
vector<ll> Num, Pnt, ql[MXM], qr[MXM];
vector<pair<ll, ll>> Q[MXM], Q2[MXM];
multiset<ll> st[MXN];//multi?
inline ll GetId(ll x){
	return upper_bound(Num.begin(), Num.end(), x) - Num.begin();
}
inline ll Getid(ll x){
	return upper_bound(Pnt.begin(), Pnt.end(), x) - Pnt.begin();
}
void Upd(ll f, ll p, ll x){
	for(; p < MXN; p += p & -p) Fen[f][p] += x;
}
ll Get(ll f, ll p){
	ll res = 0;
	for(; p; p -= p & -p) res += Fen[f][p];
	return res;
}
void Add(ll t, ll x){
	if(st[t].empty()){
		typ ++;
		Upd(0, x, +1), Upd(1, x, +1);
		st[t].insert(x);
		return;
	}
	auto itr = st[t].end(); itr --;
	if(x < *st[t].begin()){
		Upd(0, *st[t].begin(), -1);
		Upd(0, x, +1);
	}
	else if(x > *itr){
		Upd(1, *itr, -1), Upd(1, x, +1);
	}
	st[t].insert(x);
}
void Rmv(ll t, ll x){
	if(st[t].size() == 1){
		Upd(0, x, -1), Upd(1, x, -1);
		st[t].clear();
		typ --;
		return;
	}
	auto itr = st[t].find(x), ed = st[t].end();
	ed --;
	if(itr == st[t].begin()){
		Upd(0, x, -1); itr ++; 
		Upd(0, *itr, +1);
		st[t].erase(st[t].begin());
		return;
	}
	if(itr == ed){
		Upd(1, x, -1); itr --;
		Upd(1, *itr, +1);
		st[t].erase(ed);
		return;
	}
	st[t].erase(itr);
}
bool check(ll x, ll mid){
	//cout << "~\n";
	//cout << x - mid << ' ' << x + mid << '\n';
	ll l = lower_bound(Pnt.begin(), Pnt.end(), x - mid) - Pnt.begin() + 1;
	ll r = upper_bound(Pnt.begin(), Pnt.end(), x + mid) - Pnt.begin();
	//cout << l << ' ' << r << '\n';
	//cout << Get(0, r) << ' ' << Get(1, l) << '\n';
	return (Get(0, r) - Get(1, l - 1) == k);
}
void ANS(ll x, ll id){
	if(typ < k){
		Ans[id] = -1; return;
	}
	ll ind = Getid(x);
	if(ind && Pnt[ind - 1] == x && check(ind, ind)){
		Ans[id] = 0; return;
	}
	//cout << check(x, 4) << '\n';exit(0);
	ll low = 0, hig = 1e8;
	while(hig - low > 1){
		ll mid = (low + hig) / 2;
		if(check(x, mid))	hig = mid;
		else 				low = mid;
	}
	Ans[id] = hig;
	//exit(0);
}
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 >> Xs[i] >> Ts[i] >> Ls[i] >> Rs[i];
		Num.push_back(Ls[i]), Num.push_back(Rs[i]);
		Pnt.push_back(Xs[i]);
	}
	sort(Num.begin(), Num.end());
	Num.resize(unique(Num.begin(), Num.end()) - Num.begin());
	sort(Pnt.begin(), Pnt.end());
	Pnt.resize(unique(Pnt.begin(), Pnt.end()) - Pnt.begin());
	for(int i = 1; i <= n; i ++){
		Ls[i] = GetId(Ls[i]), Rs[i] = GetId(Rs[i]), Xs[i] = Getid(Xs[i]);
	}
	for(int i = 1; i <= q; i ++){
		ll x, y, z; cin >> x >> z; y = GetId(z);
		//cout << x << ' ' << y << " : ";
		if(y){
			if(Num[y - 1] == z) Q[y].push_back({x, i});// cout << "Q\n";
			else 				Q2[y].push_back({x, i});// cout << "Q1\n";
		}
		else Ans[i] = -1;
	}
	for(int i = 1; i <= n; i ++){
		ql[Ls[i]].push_back(i), qr[Rs[i]].push_back(i);
	}
	for(int i = 1; i <= Num.size(); i ++){
		for(auto j : ql[i])  Add(Ts[j], Xs[j]);// cout << "A\n";
		for(auto Pr : Q[i])  ANS(Pr.first, Pr.second);
		for(auto j : qr[i])  Rmv(Ts[j], Xs[j]);// cout << "R\n";
		for(auto Pr : Q2[i]) ANS(Pr.first, Pr.second);
	}
	for(int i = 1; i <= q; i ++) cout << Ans[i] << '\n';
	return 0;
}
//! N.N

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:123:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i = 1; i <= Num.size(); i ++){
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70768 KB Output is correct
2 Correct 39 ms 70956 KB Output is correct
3 Correct 43 ms 70848 KB Output is correct
4 Incorrect 44 ms 70852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70768 KB Output is correct
2 Correct 39 ms 70956 KB Output is correct
3 Correct 43 ms 70848 KB Output is correct
4 Incorrect 44 ms 70852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1546 ms 134116 KB Output is correct
2 Incorrect 2552 ms 127540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2723 ms 142680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70768 KB Output is correct
2 Correct 39 ms 70956 KB Output is correct
3 Correct 43 ms 70848 KB Output is correct
4 Incorrect 44 ms 70852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70768 KB Output is correct
2 Correct 39 ms 70956 KB Output is correct
3 Correct 43 ms 70848 KB Output is correct
4 Incorrect 44 ms 70852 KB Output isn't correct
5 Halted 0 ms 0 KB -