Submission #637983

#	Time	Username	Problem	Language	Result	Execution time	Memory
637983		GusterGoose27	New Home (APIO18_new_home)	C++11	100 / 100	4818 ms	1048576 KiB

new_home

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 3e5;
const int MAXV = 1e8;
 
int n, k, q;
 
class event {
public:
	int time;
	bool type; // 0 update, 1 query
	bool start_or_end; // 0 start, 1 end. Only for updates
	int store_type; // update only
	int pos; // both
	int id; // query
	event(int tim, bool se, int tp, int p) {
		time = tim;
		type = 0;
		start_or_end = se;
		store_type = tp;
		pos = p;
	}
	event(int tim, int p, int i) {
		type = 1;
		time = tim;
		pos = p;
		id = i;
	}
};
 
bool operator<(event &a, event &b) {
	return (a.time == b.time) ? (a.type < b.type) : (a.time < b.time);
}
 
vector<event> events;
int answs[MAXN];
int cnt[MAXN];
int num_active = 0;
multiset<int> locs[MAXN];
 
class stree {
public:
	stree *l = nullptr;
	stree *r = nullptr;
	int mx[2];
	multiset<int> all_vals[2]; // only for lowest level
	stree() {
		mx[0] = mx[1] = 0;
	}
	int mxq(int lv, int rv, bool lr, int lp = 0, int rp = MAXV) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return mx[lr];
		int best = 0;
		int m = (lp+rp)/2;
		if (l) best = max(best, l->mxq(lv, rv, lr, lp, m));
		if (r) best = max(best, r->mxq(lv, rv, lr, m+1, rp));
		return best;
	}
	void update(int p, int v, bool lr, int lp = 0, int rp = MAXV) {
		if (lp == rp) {
			all_vals[lr].insert(v);
			mx[lr] = *(all_vals[lr].rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree();
			l->update(p, v, lr, lp, m);
		}
		else {
			if (!r) r = new stree();
			r->update(p, v, lr, m+1, rp);
		}
		mx[lr] = 0;
		if (l) mx[lr] = max(mx[lr], l->mx[lr]);
		if (r) mx[lr] = max(mx[lr], r->mx[lr]);
	}
	void deupdate(int p, int v, bool lr, int lp = 0, int rp = MAXV) {
		if (lp == rp) {
			all_vals[lr].erase(all_vals[lr].find(v));
			if (all_vals[lr].empty()) mx[lr] = 0;
			else mx[lr] = *(all_vals[lr].rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree();
			l->deupdate(p, v, lr, lp, m);
		}
		else {
			if (!r) r = new stree();
			r->deupdate(p, v, lr, m+1, rp);
		}
		mx[lr] = 0;
		if (l) mx[lr] = max(mx[lr], l->mx[lr]);
		if (r) mx[lr] = max(mx[lr], r->mx[lr]);
	}
};
 
stree *tree;
 
void make(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		tree->update(0, r, 0);
		return;
	}
	if (r == -1) {
		tree->update(MAXV, MAXV-l, 1);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	tree->update(p2, v2, 0);
	tree->update(p1, v1, 1);
}
 
void unmake(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		tree->deupdate(0, r, 0);
		return;
	}
	if (r == -1) {
		tree->deupdate(MAXV, MAXV-l, 1);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	tree->deupdate(p2, v2, 0);
	tree->deupdate(p1, v1, 1);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k >> q;
	tree = new stree();	
	for (int i = 0; i < n; i++) {
		int x, t, a, b;
		cin >> x >> t >> a >> b; t--;
		events.push_back(event(a, 0, t, x));
		events.push_back(event(b+1, 1, t, x));
	}
	for (int i = 0; i < q; i++) {
		int x, t; cin >> x >> t;
		events.push_back(event(t, x, i));
	}
	sort(events.begin(), events.end());
	for (event ev: events) {
		if (ev.type == 0) {
			int type = ev.store_type;
			if (ev.start_or_end == 0) {
				num_active += (cnt[type] == 0);
				cnt[type]++;
				if (locs[type].find(ev.pos) != locs[type].end()) {
					locs[type].insert(ev.pos);
					continue;
				}
				auto iter = locs[type].lower_bound(ev.pos);
				int r = -1;
				int l = -1;
				if (iter != locs[type].end()) r = *iter;
				if (iter != locs[type].begin()) {
					iter--;
					l = *iter;
				}
				unmake(l, r);
				locs[type].insert(ev.pos);
				make(l, ev.pos);
				make(ev.pos, r);
			}
			else {
				cnt[type]--;
				num_active -= (cnt[type] == 0);
				locs[type].erase(locs[type].find(ev.pos));
				if (locs[type].find(ev.pos) != locs[type].end()) continue;
				auto iter = locs[type].lower_bound(ev.pos);
				int r = -1;
				int l = -1;
				if (iter != locs[type].end()) r = *iter;
				if (iter != locs[type].begin()) {
					iter--;
					l = *iter;
				}
				make(l, r);
				unmake(l, ev.pos);
				unmake(ev.pos, r);
			}
		}
		if (ev.type == 1) {
			if (num_active < k) {
				answs[ev.id] = -1;
				continue;
			}
			answs[ev.id] = max(tree->mxq(0, ev.pos, 0)-ev.pos, tree->mxq(ev.pos, MAXV, 1)-MAXV+ev.pos);
		}
	}
	for (int i = 0; i < q; i++) cout << answs[i] << "\n";
}

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