Submission #543697

#	Time	Username	Problem	Language	Result	Execution time	Memory
543697		amunduzbaev	New Home (APIO18_new_home)	C++17	0 / 100	567 ms	1048576 KiB

new_home

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define pq priority_queue

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

struct ST{
	pq<int> tree[M][2], bad[M][2];
	int f[M][2], last;
	ST(){
		last = 0;
	}
	
	void make(int x){
		if(!f[x][0]) f[x][0] = ++last;
		if(!f[x][1]) f[x][1] = ++last;
		assert(last < M);
	}
	
	void add(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1){
				tree[x][0].push(s + (lx - l));
			} else {
				tree[x][1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		make(x);
		add(l, r, s, t, lx, m, f[x][0]), add(l, r, s, t, m+1, rx, f[x][1]);
	}
	
	void bal(pq<int>& a, pq<int>& b){
		while(!a.empty() && !b.empty() && a.top() == b.top()){
			a.pop();
			b.pop();
		}
	}
	
	void del(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1){
				bad[x][0].push(s + (lx - l));
			} else {
				bad[x][1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		make(x);
		del(l, r, s, t, lx, m, f[x][0]), del(l, r, s, t, m+1, rx, f[x][1]);
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = 0;
		bal(tree[x][0], bad[x][0]);
		bal(tree[x][1], bad[x][1]);
		if(!tree[x][0].empty()) res = max(res, tree[x][0].top() + (i - lx));
		if(!tree[x][1].empty()) res = max(res, tree[x][1].top() - (i - lx));
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		if(i <= m) return max((f[x][0] ? get(i, lx, m, f[x][0]) : 0), res);
		else return max((f[x][1] ? get(i, m+1, rx, f[x][1]) : 0), res);
	}
}tree;

int x[N], t[N], a[N], b[N], l[N], y[N];
vector<int> stor[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

*/

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];
		stor[--t[i]].push_back(i);
	}
	
	bool is = 1;
	for(int i=0;i<k;i++){
		if(stor[i].empty()) { is = 0; break; }
		sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
			return (x[i] < x[j]);
		});
		for(int j=1;j<(int)stor[i].size();j++){
			int l = x[stor[i][j-1]], r = x[stor[i][j]];
			if(l == r) continue;
			int m = (l + r) >> 1;
			tree.add(l, m, 0, 1);
			tree.add(m + 1, r, r - m - 1, -1);
		}
		
		tree.add(0, x[stor[i][0]], x[stor[i][0]], -1);
		tree.add(x[stor[i].back()], MX, 0, 1);
	}
	
	while(q--){
		int l, y;
		cin>>l>>y;
		if(is){
			cout<<tree.get(l)<<"\n";
		} else {
			cout<<-1<<"\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