Submission #853701

#	Time	Username	Problem	Language	Result	Execution time	Memory
853701		flappybird	New Home (APIO18_new_home)	C++17	100 / 100	3819 ms	417184 KiB

new_home

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 1000000000
#define MOD (ll)1000000007
#define bb ' '
#define ln '\n'
template <typename T>
class Segment_Tree {
	//0-based index Segment Tree
	//O(N), O(lgN)
private:
	unsigned int N, s;
	vector<T> tree;
	vector<unsigned int> l, r;
	T query(unsigned int low, unsigned int high, unsigned int loc) {
		if (low == l[loc] && high == r[loc]) return tree[loc];
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		return query(low, r[loc * 2], loc * 2) + query(l[loc * 2 + 1], high, loc * 2 + 1);
	}
	void _update(unsigned int loc, T val) {
		loc += s;
		tree[loc] = val;
		loc /= 2;
		while (loc) {
			tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
			loc /= 2;
		}
	}
	void init(unsigned int x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = tree[x * 2] + tree[x * 2 + 1];
	}
public:
	Segment_Tree<T>() {
 
	}
	Segment_Tree<T>(vector<T>& v) {
		N = v.size();
		s = 1 << (unsigned int)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		unsigned int i;
		for (i = 0; i < N; i++) tree[i + s] = v[i];
		init();
	}
	T query(unsigned int low, unsigned int high) { return query(low, high, 1); }
	void update(unsigned int location, T new_value) { _update(location, new_value); }
};
struct dat {
	ll x, t, a, b;
	dat() {}
	dat(ll x, ll t, ll a, ll b) :x(x), t(t), a(a), b(b) {}
	bool operator<(dat d) {
		if (t != d.t) return t < d.t;
		if (x != d.x) return x < d.x;
		if (a != d.a) return a < d.a;
		return b < d.b;
	}
};
struct Query {
	ll l, y, num;
	Query() {}
	Query(ll l, ll y, ll num) :l(l), y(y), num(num) {}
	bool operator<(Query q) {
		return y < q.y;
	}
};
map<ll, vector<dat>> arr;
multiset<ll> st[MAX];
vector<Query> query;
ll ans[MAX];
vector<ll> point, tarr;
vector<pll> larr;
vector<pair<ll, pair<ll, pll>>> qlog;
ll chk[MAX];
struct node {
	ll x, y;
	ll lv, rv;
	node() :x(0), y(0), lv(0), rv(-INF) {}
	node(ll x, ll y) :x(x), y(y) {
		lv = x + y;
		rv = y - x;
	}
	node(ll x, ll y, ll lv, ll rv) :x(x), y(y), lv(lv), rv(rv) {}
	node operator+(node x) { return node(0, 0, max(lv, x.lv), max(rv, x.rv)); }
};
bool operator<(pll p1, pll p2) {
	if (p1.first == p2.first) return p1.second < p2.second;
	return p1.first < p2.first;
}
ll getind(pll x) {
	return lower_bound(larr.begin(), larr.end(), x) - larr.begin();
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, K, Q;
	cin >> N >> K >> Q;
	ll i;
	ll x, t, a, b;
	vector<dat> datset;
	for (i = 1; i <= N; i++) {
		cin >> x >> t >> a >> b;
		arr[a].push_back(dat(x, t, a, b));
		arr[b + 1].push_back(dat(x, t, a, b));
		tarr.push_back(a);
		tarr.push_back(b + 1);
	}
	for (i = 0; i < Q; i++) {
		cin >> a >> b;
		query.push_back(Query(a, b, i));
	}
	sort(query.begin(), query.end());
	//simulation
	for (i = 1; i <= K; i++) st[i].insert(-INF);
	for (i = 1; i <= K; i++) st[i].insert(INF);
	map<ll, vector<dat>>::iterator it;
	for (it = arr.begin(); it != arr.end(); it++) {
		t = it->first;
		for (auto d : it->second) {
			ll pv = *prev(st[d.t].lower_bound(d.x));
			ll ne = *st[d.t].upper_bound(d.x);
			if (d.a == t) st[d.t].insert(d.x);
			else st[d.t].erase(st[d.t].find(d.x));
			larr.emplace_back(pv + ne, d.t);
			larr.emplace_back(pv + d.x, d.t);
			larr.emplace_back(d.x + ne, d.t);
		}
	}
	Segment_Tree<node> segtree;
	vector<node> v(larr.size());
	segtree = Segment_Tree<node>(v);
	it = arr.begin();
	ll cnt = 0;
	sort(larr.begin(), larr.end());
	larr.erase(unique(larr.begin(), larr.end()), larr.end());
	for (i = 0; i < Q; i++) {
		Query q = query[i];
		while (it != arr.end()) {
			ll t = it->first;
			if (t > q.y) break;
			for (auto d : it->second) {
				ll pv = *prev(st[d.t].lower_bound(d.x));
				ll ne = *st[d.t].upper_bound(d.x);
				if (d.a == t) {
					segtree.update(getind({ pv + ne, d.t }), node(pv + ne, 0));
					segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, d.x - pv));
					segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, ne - d.x));
					st[d.t].insert(d.x);
					if (!chk[d.t]) cnt++;
					chk[d.t]++;
				}
				else {
					st[d.t].erase(st[d.t].find(d.x));
					if (chk[d.t] == 1) cnt--;
					chk[d.t]--;
					if (st[d.t].find(d.x) != st[d.t].end()) continue;
					segtree.update(getind({ pv + ne, d.t }), node(pv + ne, ne - pv));
					segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, 0));
					segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, 0));
				}
			}
			it++;
		}
		if (cnt != K) {
			ans[q.num] = -1;
			continue;
		}
		node l = segtree.query(0, getind({ 2 * q.l, 10101010 }) - 1);
		node r = segtree.query(getind({ 2 * q.l, -1 }), larr.size() - 1);
		ans[q.num] = max(l.lv - 2 * q.l, r.rv + 2 * q.l) / 2;
	}
	for (i = 0; i < Q; i++) cout << ans[i] << ln;
	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