Submission #985064

#	Time	Username	Problem	Language	Result	Execution time	Memory
985064		qwerasdfzxcl	New Home (APIO18_new_home)	C++17	80 / 100	5035 ms	297468 KiB

new_home

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int INF = 1e9 + 100;

struct SegLeft{

	vector<int> X;
	int tree[600600], sz;

	pair<int, int> buf[10001000];
	int lsz;

	inline void push(int i, int x){
		if (tree[i] <= x) return;
		buf[lsz++] = {i, tree[i]};
		tree[i] = x;
	}

	inline void pop(){
		--lsz;
		tree[buf[lsz].first] = buf[lsz].second;
	}

	void init(const vector<int> &_X){
		X = _X;
		sz = X.size();
		lsz = 0;
		fill(tree, tree+sz*2, INF);
	}

	void update(int l, int r, int x){
		l = lower_bound(X.begin(), X.end(), l) - X.begin();
		r = upper_bound(X.begin(), X.end(), r) - X.begin();

		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1){
				push(l, x);
				l++;
			}
			if (r&1){
				--r;
				push(r, x);
			}
		}
	}

	int query(int p){
		p = lower_bound(X.begin(), X.end(), p) - X.begin();
		
		int ret = INF;
		for (p+=sz;p;p>>=1) ret = min(ret, tree[p]);

		return ret;
	}

	void rollback(int lsz0){
		while(lsz > lsz0) pop();
	}

}treeL;

struct SegRight{

	vector<int> X;
	int tree[600600], sz;

	pair<int, int> buf[10001000];
	int lsz;

	inline void push(int i, int x){
		if (tree[i] >= x) return;
		buf[lsz++] = {i, tree[i]};
		tree[i] = x;
	}

	inline void pop(){
		--lsz;
		tree[buf[lsz].first] = buf[lsz].second;
	}

	void init(const vector<int> &_X){
		X = _X;
		sz = X.size();
		lsz = 0;
		fill(tree, tree+sz*2, -INF);
	}

	void update(int l, int r, int x){
		l = lower_bound(X.begin(), X.end(), l) - X.begin();
		r = upper_bound(X.begin(), X.end(), r) - X.begin();

		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1){
				push(l, x);
				l++;
			}
			if (r&1){
				--r;
				push(r, x);
			}
		}
	}

	int query(int p){
		p = lower_bound(X.begin(), X.end(), p) - X.begin();
		
		int ret = -INF;
		for (p+=sz;p;p>>=1) ret = max(ret, tree[p]);

		return ret;
	}

	void rollback(int lsz0){
		while(lsz > lsz0) pop();
	}

}treeR;

int pos[300300], col[300300], a[300300], b[300300];
int posQ[300300], tQ[300300], ans[300300];
vector<int> T, X, buf[1201200], bufQ[300300];
multiset<int> st[300300];

void insert(int i, int l, int r, int s, int e, int x){
	if (r<s || e<l) return;
	if (s<=l && r<=e){
		buf[i].push_back(x);
		return;
	}

	int m = (l+r)>>1;
	insert(i<<1, l, m, s, e, x);
	insert(i<<1|1, m+1, r, s, e, x);
}

void dnc(int i, int l, int r){
	int szL = treeL.lsz, szR = treeR.lsz;
	for (auto &idx:buf[i]){
		int c = col[idx], p = pos[idx];
		auto iter = st[c].find(p);
		auto niter = next(iter);

		if (iter==st[c].begin()){
			if (niter==st[c].end()){
				treeL.update(-INF, INF, -INF);
			}

			else{
				treeR.update(-INF, *niter, *niter);
			}
		}

		else{
			auto piter = prev(iter);
			if (niter==st[c].end()){
				treeL.update(*piter, INF, *piter);
			}

			else{
				int mid = (*piter + *niter) / 2;
				treeL.update(*piter, mid, *piter);
				treeR.update(mid+1, *niter, *niter);
			}
		}

		st[c].erase(iter);
	}

	if (l==r){
		for (auto &idx:bufQ[l]){
			int pl = treeL.query(posQ[idx]);
			int pr = treeR.query(posQ[idx]);

			if (pl==-INF || pr==INF) ans[idx] = -1;
			else ans[idx] = max(posQ[idx]-pl, pr-posQ[idx]);
		}
	}

	else{
		int m = (l+r)>>1;
		dnc(i<<1, l, m);
		dnc(i<<1|1, m+1, r);
	}

	for (auto &idx:buf[i]) st[col[idx]].insert(pos[idx]);
	treeL.rollback(szL);
	treeR.rollback(szR);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k, q;
	cin >> n >> k >> q;

	for (int i=1;i<=n;i++){
		cin >> pos[i] >> col[i] >> a[i] >> b[i];
	}

	for (int i=1;i<=q;i++){
		cin >> posQ[i] >> tQ[i];
		T.push_back(tQ[i]);
		X.push_back(posQ[i]);
	}

	sort(T.begin(), T.end());
	T.erase(unique(T.begin(), T.end()), T.end());
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	treeL.init(X); treeR.init(X);

	for (int i=1;i<=q;i++){
		tQ[i] = lower_bound(T.begin(), T.end(), tQ[i]) - T.begin() + 1;
		bufQ[tQ[i]].push_back(i);

		// printf(" ok t = %d\n", i);
	}

	for (int i=1;i<=n;i++){
		a[i] = lower_bound(T.begin(), T.end(), a[i]) - T.begin() + 1;
		b[i] = upper_bound(T.begin(), T.end(), b[i]) - T.begin() + 1;

		// printf(" ok remove (%d, %d) and (%d, %d)\n", 1, a[i]-1, b[i], (int)T.size());

		insert(1, 1, T.size(), 1, a[i]-1, i);
		insert(1, 1, T.size(), b[i], T.size(), i);
	} 

	for (int i=1;i<=n;i++){
		st[col[i]].insert(pos[i]);
	}

	for (int i=1;i<=k;i++){
		if (st[i].empty()) {treeL.update(-INF, INF, -INF); continue;}

		int p = -INF;
		for (auto x:st[i]){
			if (p==-INF) treeR.update(-INF, x, x);
			else{
				int mid = (p+x)/2;
				treeL.update(p, mid, p);
				treeR.update(mid+1, x, x);	
			}

			p = x;
		}

		treeL.update(p, INF, p);
	}
	dnc(1, 1, T.size());

	for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
}

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