Submission #566063

#	Time	Username	Problem	Language	Result	Execution time	Memory
566063		ngpin04	New Home (APIO18_new_home)	C++14	100 / 100	4221 ms	243628 KiB

new_home

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 6e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct event {
	int y,id,t;
	event(int _y = 0, int _id = 0, int _t = 0) {
		y = _y;
		id = _id;
		t = _t;
	}

	bool operator < (const event &e) const {
		return y < e.y || (y == e.y && t < e.t);	
	}
};

struct segtree {
	bool mx;
	int n;
	vector <int> st;

	segtree(int _n = 0, bool _mx = 0) {
		mx = _mx;
		n = _n;
		st.assign((n << 2) + 5, mx ? -oo : oo);
	}	

	void update(int id, int l, int r, int pos, int val) {
		if (l > pos || r < pos)
			return;
		if (l == r) {
			st[id] = val;
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, pos, val);
		update(id << 1 | 1, mid + 1, r, pos, val);
		if (mx) 
			st[id] = max(st[id << 1], st[id << 1 | 1]);
		else
			st[id] = min(st[id << 1], st[id << 1 | 1]);
	}

	void update(int pos, int val) {
		update(1, 1, n, pos, val);
	}

	int getminl(int id, int l, int r, int x) {
		if (st[id] < x)
			return oo;
		if (l == r)
			return l;
		int mid = (l + r) >> 1;
		int res = getminl(id << 1, l, mid, x);
		if (res == oo)
			res = getminl(id << 1 | 1, mid + 1, r, x);
		return res;
	}

	int getminl(int x) {
		return getminl(1, 1, n, x);
	}

	int getmaxr(int id, int l, int r, int x) {
		if (st[id] > x)
			return -oo;
		if (l == r)
			return l;
		int mid = (l + r) >> 1;
		int res = getmaxr(id << 1 | 1, mid + 1, r, x);
		if (res == -oo)
			res = getmaxr(id << 1, l, mid, x);
		return res;
	}

	int getmaxr(int x) {
		return getmaxr(1, 1, n, x);
	}
};	

segtree minl, maxr;

multiset <int> candl[N];
multiset <int> candr[N];
multiset <int> pos[N];

vector <event> events;
vector <int> pos_x;

int ans[N];
int _x[N];	
int t[N];
int n,k,q,sz,cnt;

int getind(int x) {
	return upper_bound(ALL(pos_x), x) - pos_x.begin();
}

int getans(int x) {
	int pos = getind(x);
	int l = minl.getminl(pos);
	int r = maxr.getmaxr(pos);
	int res = -1;
	if (l <= pos)
		maxi(res, pos_x[pos - 1] - pos_x[l - 1]);
	if (pos <= r)
		maxi(res, pos_x[r - 1] - pos_x[pos - 1]);
	return res;
}

void updatemax(int pos) {
	maxr.update(pos, *candr[pos].begin());
}

void updatemin(int pos) {
	minl.update(pos, *prev(candl[pos].end()));
}

void add(int l, int r, int t) {
	int mid = (l + r) >> 1;
	int pl = getind(l);
	int pr = getind(r);
	int pmid = getind(mid);

	if (t > 0) {
		candl[pl].insert(pmid);
		updatemin(pl);
		if (pmid < pr) {
			candr[pr].insert(pmid + 1);
			updatemax(pr);
		}
	} else {
		candl[pl].erase(candl[pl].find(pmid));
		updatemin(pl);
		if (pmid < pr) {
			candr[pr].erase(candr[pr].find(pmid + 1));
			updatemax(pr);
		}
	}
}

void solve(vector <pair <int, int>> events) {
	for (pair <int, int> pir : events) {
		// cerr << cnt << "\n";
		int x = _x[pir.fi];
		int c = t[pir.fi];
		int p = getind(x);

		// cerr << pir.fi << " " << pir.se << " " << x << " " << c << "\n";

		if (pir.se == 2) {
			ans[pir.fi - n] = (cnt < k) ? -1 : getans(x);
			// cerr << "ans = " << ans[pir.fi - n] << "\n";
		} else if (pir.se == 0) {
			if (!pos[c].size()) {
				cnt++;			
				candr[p].insert(1);
				candl[p].insert(sz);

				updatemax(p);
				updatemin(p);
				pos[c].insert(x);
				continue;
			}

			auto it = pos[c].lower_bound(x);
			if (it == pos[c].begin()) {
				int tmp = getind(*it);

				candr[tmp].erase(candr[tmp].find(1));
				candr[p].insert(1);

				updatemax(tmp);
				updatemax(p);

				add(x, *it, 1);
				pos[c].insert(x);
				continue;
			} 

			if (it == pos[c].end()) {
				it--;
				int tmp = getind(*it);
				
				candl[tmp].erase(candl[tmp].find(sz));
				candl[p].insert(sz);
				
				updatemin(tmp);
				updatemin(p);

				add(*it, x, 1);
				pos[c].insert(x);
				continue;
			}

			int l = *prev(it);
			int r = *it;
			add(l, r, -1);
			add(l, x, 1);
			add(x, r, 1);
			
			pos[c].insert(x);
		} else {
			pos[c].erase(pos[c].find(x));

			if (!pos[c].size()) {
				candr[p].erase(candr[p].find(1));
				candl[p].erase(candl[p].find(sz));

				updatemax(p);
				updatemin(p);

				cnt--;
				continue;
			}

			auto it = pos[c].lower_bound(x);
			if (it == pos[c].begin()) {
				int tmp = getind(*it);

				candr[tmp].insert(1);
				candr[p].erase(candr[p].find(1));

				updatemax(p);
				updatemax(tmp);

				add(x, *it, -1);
				continue;
			} 

			if (it == pos[c].end()) {
				it--;	
				int tmp = getind(*it);

				candl[tmp].insert(sz);
				candl[p].erase(candl[p].find(sz));
				
				updatemin(p);
				updatemin(tmp);
				add(*it, x, -1);
				continue;
			}

			int l = *prev(it);
			int r = *it;
			add(l, r, 1);
			add(l, x, -1);
			add(x, r, -1);
		}
	}
}	

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) {
		int a,b;
		cin >> _x[i] >> t[i] >> a >> b;
		events.push_back(event(a, i, 0));
		events.push_back(event(b + 1, i, 1));
		pos_x.push_back(_x[i]);
	}

	for (int i = 1; i <= q; i++) {
		int y; 
		cin >> _x[n + i] >> y;
		events.push_back(event(y, n + i, 2));
		pos_x.push_back(_x[n + i]);
	}
	sort(ALL(pos_x));
	sz = n + q;
	minl = segtree(sz, 1);
	maxr = segtree(sz, 0);

	for (int i = 1; i <= sz; i++) {
		candl[i].insert(-oo);
		candr[i].insert(oo);
	}

	sort(ALL(events));
	for (int l = 0; l < (int) events.size();) {
		int r = l;
		while (r < (int) events.size() && events[l].y == events[r].y)
			r++;

		vector <pair <int, int>> pir;
		for (int i = l; i < r; i++)
			pir.push_back(mp(events[i].id, events[i].t));

		solve(pir);
		l = r;
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
	return 0;
}

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