Submission #637978

#	Time	Username	Problem	Language	Result	Execution time	Memory
637978		GusterGoose27	New Home (APIO18_new_home)	C++11	47 / 100	4388 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:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int mx;
	multiset<int> all_vals; // only for lowest level
	stree(int lv, int rv) {
		mx = 0;
		lp = lv;
		rp = rv;
	}
	int mxq(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return mx;
		int best = 0;
		if (l) best = max(best, l->mxq(lv, rv));
		if (r) best = max(best, r->mxq(lv, rv));
		return best;
	}
	void update(int p, int v) {
		if (lp == rp) {
			all_vals.insert(v);
			mx = *(all_vals.rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree(lp, m);
			l->update(p, v);
		}
		else {
			if (!r) r = new stree(m+1, rp);
			r->update(p, v);
		}
		mx = 0;
		if (l) mx = max(mx, l->mx);
		if (r) mx = max(mx, r->mx);
	}
	void deupdate(int p, int v) {
		if (lp == rp) {
			all_vals.erase(all_vals.find(v));
			if (all_vals.empty()) mx = 0;
			else mx = *(all_vals.rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree(lp, m);
			l->deupdate(p, v);
		}
		else {
			if (!r) r = new stree(m+1, rp);
			r->deupdate(p, v);
		}
		mx = 0;
		if (l) mx = max(mx, l->mx);
		if (r) mx = max(mx, r->mx);
	}
};

stree *ltree, *rtree;

void make(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		ltree->update(0, r);
		return;
	}
	if (r == -1) {
		rtree->update(MAXV, MAXV-l);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	ltree->update(p2, v2);
	rtree->update(p1, v1);
}

void unmake(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		ltree->deupdate(0, r);
		return;
	}
	if (r == -1) {
		rtree->deupdate(MAXV, MAXV-l);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	ltree->deupdate(p2, v2);
	rtree->deupdate(p1, v1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k >> q;
	ltree = new stree(0, MAXV);
	rtree = new stree(0, MAXV);	
	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(ltree->mxq(0, ev.pos)-ev.pos, rtree->mxq(ev.pos, MAXV)-MAXV+ev.pos);
		}
	}
	for (int i = 0; i < q; i++) cout << answs[i] << "\n";
}

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