Submission #544093

#	Time	Username	Problem	Language	Result	Execution time	Memory
544093		amunduzbaev	New Home (APIO18_new_home)	C++17	0 / 100	5028 ms	434424 KiB

new_home

#include "bits/stdc++.h"
using namespace std;

#define ar array

const int MX = 1e8 + 5;
const int N = 3e5 + 5;
const int M = 9e5 + 5;

struct BIT{
	multiset<int> tree[M];
	
	void add(int i, int r){
		//~ if(!i){
			//~ cout<<i<<endl;
		//~ }
		for(;i<M;i+=(i&-i)) tree[i].insert(r);
	}
	
	void del(int i, int r){
		//~ if(!i){
			//~ cout<<i<<endl;
		//~ }
		for(;i<M;i+=(i&-i)) tree[i].erase(tree[i].find(r));
	}
	
	int get(int i){
		int r=0;
		for(;i>0;i-=(i&-i)){
			if(!tree[i].empty()) r = max(r, *tree[i].rbegin());
		} return r;
	}
}tree;

int x[N], t[N], a[N], b[N];
int l[N], y[N];
multiset<int> ss[N];

/*

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

*/

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		t[i]--, b[i]++;
	}
	
	for(int i=0;i<q;i++){
		cin>>l[i]>>y[i];
	}
	
	vector<int> in(n); iota(in.begin(), in.end(), 0);
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	
	sort(in.begin(), in.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	
	sort(out.begin(), out.end(), [&](int i, int j){
		return (b[i] < b[j]);
	});
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (y[i] < y[j]);
	});
	
	vector<int> tot = {0, MX};
	for(int i=0;i<n;i++) tot.push_back(x[i]);
	int c = k;
	{
		auto cret = [&](int i){
			auto it = ss[t[i]].upper_bound(x[i]);
			if(ss[t[i]].empty()) c--;
			if(it == ss[t[i]].end()){
				if(it != ss[t[i]].begin()){
					it--;
					tot.push_back((*it + x[i]) >> 1);
				}
			} else {
				if(it == ss[t[i]].begin()){
					tot.push_back((x[i] + *it) >> 1);
				} else {
					auto R = it; it--;
					tot.push_back((*it + x[i]) >> 1);
					tot.push_back((x[i] + *R) >> 1);
				}
			}
			
			ss[t[i]].insert(x[i]);
		};
		
		auto ecrt = [&](int i){
			ss[t[i]].erase(ss[t[i]].find(x[i]));
			if(ss[t[i]].empty()) c++;
			auto it = ss[t[i]].upper_bound(x[i]);
			if(it != ss[t[i]].end()){
				if(it != ss[t[i]].begin()){
					auto R = it; it--;
					tot.push_back((*it + *R) >> 1);
				}
			}
		};
		
		int I = 0, O = 0;
		for(auto i : p){
			while(I < n && a[in[I]] <= y[i]){
				//~ In(in[I++]);
				cret(in[I++]);
			}
			
			while(O < n && b[out[O]] <= y[i]){
				//~ Out(out[O++]);
				ecrt(out[O++]);
			}
		}
		while(I < n) cret(in[I++]);
		while(O < n) ecrt(out[O++]);
	}
	
	sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	vector<int> res(q, -1);
	
	auto solve = [&](){
		int I = 0, O = 0, c = k;
		
		auto add = [&](int l, int r){
			if(l == r) return;
			int m = (l + r) >> 1;
			l = upper_bound(tot.begin(), tot.end(), l) - tot.begin();
			tree.add(l, m);
			//~ cout<<l<<" "<<m<<"\n";
		}; auto dec = [&](int x) { 
			tree.add(1, x); 
			//~ cout<<1<<" "<<x<<"\n";
		};

		auto dadd = [&](int l, int r){
			if(l == r) return;
			int m = (l + r) >> 1;
			l = upper_bound(tot.begin(), tot.end(), l) - tot.begin();
			tree.del(l, m);
		}; auto ddec = [&](int x) { 
			tree.del(1, x);
		};
		
		auto In = [&](int i){
			auto it = ss[t[i]].upper_bound(x[i]);
			if(ss[t[i]].empty()) c--;
			if(it == ss[t[i]].end()){
				if(it != ss[t[i]].begin()){
					it--;
					//~ dinc(*it);
					add(*it, x[i]);
					//~ inc(x[i]);
				} else {
					//~ inc(x[i]);
					dec(x[i]);
				}
			} else {
				if(it == ss[t[i]].begin()){
					ddec(*it);
					add(x[i], *it);
					dec(x[i]);
				} else {
					auto R = it; it--;
					dadd(*it, *R);
					add(*it, x[i]);
					add(x[i], *R);
				}
			}
			
			ss[t[i]].insert(x[i]);
		};
		
		auto Out = [&](int i){
			ss[t[i]].erase(ss[t[i]].find(x[i]));
			if(ss[t[i]].empty()) c++;
			auto it = ss[t[i]].upper_bound(x[i]);
			if(it == ss[t[i]].end()){
				if(it == ss[t[i]].begin()){
					//~ dinc(x[i]);
					ddec(x[i]);
				} else {
					it--;
					dadd(*it, x[i]);
					//~ dinc(x[i]);
					//~ inc(*it);
				}
			} else {
				if(it == ss[t[i]].begin()){
					dadd(x[i], *it);
					ddec(x[i]);
					dec(*it);
				} else {
					auto R = it; it--;
					dadd(*it, x[i]);
					dadd(x[i], *R);
					add(*it, *R);
				}
			}
		};
		
		for(auto i : p){
			while(I < n && a[in[I]] <= y[i]){
				//~ In(in[I++]);
				In(in[I++]);
			}
			
			while(O < n && b[out[O]] <= y[i]){
				//~ Out(out[O++]);
				Out(out[O++]);
			}
			
			int P = upper_bound(tot.begin(), tot.end(), l[i]) - tot.begin();
			//~ cout<<P<<"\n";
			if(!c) res[i] = max(res[i], tree.get(P) - l[i]);
		}
		
		while(I < n) In(in[I++]);
		while(O < n) Out(out[O++]);
	};
	
	solve();
	for(int i=0;i<n;i++) x[i] = MX - x[i];
	for(int i=0;i<q;i++) l[i] = MX - l[i];
	for(auto& x : tot) x = MX - x;
	reverse(tot.begin(), tot.end());
	solve();
	//~ cout<<"here"<<endl;
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20