Submission #566027

#	Time	Username	Problem	Language	Result	Execution time	Memory
566027		ngpin04	New Home (APIO18_new_home)	C++14	47 / 100	5058 ms	531756 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);	
	}
};

multiset <int> st[2][N << 2];
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();
}

void update(int id, int l, int r, int u, int v, int val, int t) {
	if (l > v || r < u)
		return;
	if (l >= u && r <= v) {
		if (t > 0)
			st[t - 1][id].insert(val);
		else
			st[(-t) - 1][id].erase(st[(-t) - 1][id].find(val));
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, u, v, val, t);
	update(id << 1 | 1, mid + 1, r, u, v, val, t);
}

void update(int l, int r, int val, int t) {
	// cerr << "update " << l << " " << r << " " << val << " " << t << "\n";
	update(1, 1, sz, l, r, val, t);
}

pair <int, int> getans(int id, int l, int r, int pos) {
	if (l > pos || r < pos)
		return mp(oo, -oo);

	int mx = -oo, mn = oo;
	if (st[0][id].size())
		mn = *st[0][id].begin();
	if (st[1][id].size())
		mx = *prev(st[1][id].end());

	if (l == r)
		return mp(mn, mx);
	int mid = (l + r) >> 1;
	pair <int, int> pir;

	pir = getans(id << 1, l, mid, pos);
	mini(mn, pir.fi);
	maxi(mx, pir.se);

	pir = getans(id << 1 | 1, mid + 1, r, pos);
	mini(mn, pir.fi);
	maxi(mx, pir.se);
	return mp(mn, mx);
}

int getans(int x) {
	int pos = getind(x);
	pair <int, int> pir = getans(1, 1, sz, pos);
	int minl = pir.fi;
	int maxr = pir.se;
	if (minl == oo && maxr == -oo)
		return -1;
	int res = 0;
	maxi(res, pos_x[pos - 1] - minl);
	maxi(res, maxr - pos_x[pos - 1]);
	return res;
}

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);
	update(pl, pmid, l, t * 1);
	if (pmid < pr)
		update(pmid + 1, pr, r, t * 2);
}

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++;			
				update(1, p, x, 2);
				update(p, sz, x, 1);
				pos[c].insert(x);
				continue;
			}

			auto it = pos[c].lower_bound(x);
			if (it == pos[c].begin()) {
				int tmp = getind(*it);
				update(1, tmp, *it, -2);
				update(1, p, x, 2);
				add(x, *it, 1);
				pos[c].insert(x);
				continue;
			} 

			if (it == pos[c].end()) {
				it--;
				int tmp = getind(*it);
				update(tmp, sz, *it, -1);
				update(p, sz, x, 1);
				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()) {
				update(1, p, x, -2);
				update(p, sz, x, -1);
				cnt--;
				continue;
			}

			auto it = pos[c].lower_bound(x);
			if (it == pos[c].begin()) {
				int tmp = getind(*it);
				update(1, tmp, *it, 2);
				update(1, p, x, -2);
				add(x, *it, -1);
				continue;
			} 

			if (it == pos[c].end()) {
				it--;	
				int tmp = getind(*it);
				update(tmp, sz, *it, 1);
				update(p, sz, x, -1);
				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;

	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: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20