Submission #625203

#	Time	Username	Problem	Language	Result	Execution time	Memory
625203		QwertyPi	New Home (APIO18_new_home)	C++14	47 / 100	4959 ms	459472 KiB

new_home

#include <bits/stdc++.h>

const int N = 300013;
using namespace std;

struct Store{
	int x, ty, a, b;
};

struct Query{
	int t, ty, x, id;
};

struct Pair{
	Pair() = default;
	Pair(int _x, int _y, int _d) : x(_x), y(_y), d(_d){};
	int x, y, d;
};

struct DS{
	vector<int> sp[N], bits[N];
	string name;
	DS() = default;
	DS(string _n) : name(_n){}
	void insert(Pair p){
		int x = p.x + 1, y = p.y + 1;
		for(int i = x; i < N; i += i & -i){
			sp[i].push_back(y);
		}
	}
	void parse(){
		for(int i = 0; i < N; i++) sp[i].push_back(0);
		for(int i = 0; i < N; i++){
			sort(sp[i].begin(), sp[i].end());
			sp[i].resize(unique(sp[i].begin(), sp[i].end()) - sp[i].begin());
			bits[i].resize(sp[i].size());
		}
	}
	void add(Pair p){
		int x = p.x + 1, y = p.y + 1;
		for(int i = x; i < N; i += i & -i){
			int idx = lower_bound(sp[i].begin(), sp[i].end(), y) - sp[i].begin();
			for(int j = idx; j < sp[i].size(); j += j & -j){
				bits[i][j] += p.d;
			}
		}
	}
	int qry(int x, int y){
		x++; y++;
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			int idx = upper_bound(sp[i].begin(), sp[i].end(), y) - 1 - sp[i].begin();
			for(int j = idx; j; j -= j & -j){
				ret += bits[i][j];
			}
		}
		return ret;
	}
	int qry(int x1, int x2, int y1, int y2){
		return qry(x2, y2) + qry(x1 - 1, y1 - 1) - qry(x2, y1 - 1) - qry(x1 - 1, y2);
	}
} ds;

struct BIT{
	int bit[N];
	void add(int p, int v){
		p++;
		for(int i = p; i < N; i += i & -i){
			bit[i] += v;
		}
	}
	int qry(int p){
		int ret = 0;
		p++;
		for(int i = p; i; i -= i & -i){
			ret += bit[i];
		}
		return ret;
	}
	int qry(int l, int r){
		return qry(r) - qry(l - 1);
	}
} bit;

vector<Store> stores;
vector<Query> Q;
vector<Pair> C[N * 3], D[N * 3];
int m;
int p[N * 2];
int ans[N];

int n, k, q;

bool check(int x1, int x2){
	int l = lower_bound(p, p + m, x1) - p;
	int r = upper_bound(p, p + m, x2) - 1 - p;
	int c1 = bit.qry(l, r);
	int c2 = ds.qry(l, r, l, r);
	assert(c1 - c2 >= 0 && c1 - c2 <= k);
	return c1 - c2 == k;
}

int qry(int x){
	int l = 0, r = 1e9;
	while(l != r){
		int mid = (l + r) / 2;
		if(check(p[x] - mid, p[x] + mid)){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	return l >= 9e8 ? -1 : l;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	vector<int> sp;
	for(int i = 0; i < n; i++){
		int x, ty, a, b;
		cin >> x >> ty >> a >> b;
		stores.push_back({x, ty, a, b + 1}); 
		sp.push_back(a);
		sp.push_back(b + 1);
	}
	for(int i = 0; i < q; i++){
		int x, t;
		cin >> x >> t;
		Q.push_back({t, 2, x, i});
	}
	sort(sp.begin(), sp.end());
	sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
	{
		map<int, int> M;
		for(int i = 0; i < sp.size(); i++){
			M[sp[i]] = i;
		}
		for(auto& st : stores){
			st.a = M[st.a];
			st.b = M[st.b];
		}
		for(auto& q : Q){
			q.t = upper_bound(sp.begin(), sp.end(), q.t) - sp.begin() - 1; 
		}
	}
	{
		vector<int> xs;
		for(auto st : stores){
			xs.push_back(st.x);
		}
		for(auto q : Q){
			xs.push_back(q.x);
		}
		sort(xs.begin(), xs.end());
		xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
		m = xs.size();
		for(int i = 0; i < m; i++){
			p[i] = xs[i];
		}
		map<int, int> M;
		for(int i = 0; i < m; i++){
			M[xs[i]] = i;
		}
		for(auto& st : stores){
			st.x = M[st.x];
		}
		for(auto& q : Q){
			q.x = M[q.x];
		}
	}
	for(auto st : stores){
		Q.push_back({st.a, 1, st.x, st.ty});
		Q.push_back({st.b, 0, st.x, st.ty});
	}
	
	sort(Q.begin(), Q.end(), [](Query a, Query b){
		return a.t < b.t || a.t == b.t && a.ty < b.ty;
	});
	multiset<int> vset[N];
	for(int i = 0; i < Q.size(); i++){
		Query q = Q[i];
		auto ptr = vset[q.id].begin();
		switch(q.ty){
			case 0:
				ptr = vset[q.id].lower_bound(q.x);
				assert(ptr != vset[q.id].end());
				if(ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), *ptr, -1});
				if(next(ptr) != vset[q.id].end()) C[i].push_back({*ptr, *next(ptr), -1});
				if(ptr != vset[q.id].begin() && next(ptr) != vset[q.id].end()) C[i].push_back({*prev(ptr), *next(ptr), 1});
				D[i].push_back({q.x, -1, -1});
				vset[q.id].erase(ptr);
				break;
			case 1:
				ptr = vset[q.id].lower_bound(q.x);
				if(ptr != vset[q.id].end() && ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), *ptr, -1});
				if(ptr != vset[q.id].end()) C[i].push_back({q.x, *ptr, 1});
				if(ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), q.x, 1});
				D[i].push_back({q.x, -1, 1});
				vset[q.id].insert(q.x);
				break;
			case 2:
				break;
			default:
				assert(false);
		}
	}
	for(int i = 0; i < Q.size(); i++){
		for(auto p : C[i]){
			ds.insert(p);
		}
	}
	ds.parse();
	for(int i = 0; i < Q.size(); i++){
		for(auto p : C[i]){
			ds.add(p);
		}
		for(auto p : D[i]){
			bit.add(p.x, p.d);
		}
		Query q = Q[i];
		switch(q.ty){
			case 0:
				break;
			case 1:
				break;
			case 2: ans[q.id] = qry(q.x); break;
			default: assert(false);
		}
	}
	for(int i = 0; i < q; i++){
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

new_home.cpp: In member function 'void DS::add(Pair)':
new_home.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for(int j = idx; j < sp[i].size(); j += j & -j){
      |                     ~~^~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int i = 0; i < sp.size(); i++){
      |                  ~~^~~~~~~~~~~
new_home.cpp: In lambda function:
new_home.cpp:179:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  179 |   return a.t < b.t || a.t == b.t && a.ty < b.ty;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:182:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |  for(int i = 0; i < Q.size(); i++){
      |                 ~~^~~~~~~~~~
new_home.cpp:209:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |  for(int i = 0; i < Q.size(); i++){
      |                 ~~^~~~~~~~~~
new_home.cpp:215:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |  for(int i = 0; i < Q.size(); i++){
      |                 ~~^~~~~~~~~~

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