oj.uz

Submission #469869

# Submission time Handle Problem Language Result Execution time Memory
469869 2021-09-02T07:52:46 Z flappybird New Home (APIO18_new_home) C++14
10 / 100
 4449 ms 219028 KB 
#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;
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) {
				larr.emplace_back(pv + ne, d.t);
				larr.emplace_back(pv + d.x, d.t);
				larr.emplace_back(d.x + ne, d.t);
				st[d.t].insert(d.x);
			}
			else st[d.t].erase(st[d.t].find(d.x));
		}
	}
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14468 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14796 KB Output is correct
6 Incorrect 10 ms 14732 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14468 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14796 KB Output is correct
6 Incorrect 10 ms 14732 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2541 ms 194660 KB Output is correct
2 Correct 2813 ms 187356 KB Output is correct
3 Correct 2339 ms 219028 KB Output is correct
4 Correct 2667 ms 198708 KB Output is correct
5 Correct 2859 ms 186840 KB Output is correct
6 Correct 2618 ms 187352 KB Output is correct
7 Correct 1654 ms 219028 KB Output is correct
8 Correct 1962 ms 198836 KB Output is correct
9 Correct 2036 ms 191588 KB Output is correct
10 Correct 2305 ms 187948 KB Output is correct
11 Correct 1493 ms 185696 KB Output is correct
12 Correct 1503 ms 187288 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4449 ms 216956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14468 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14796 KB Output is correct
6 Incorrect 10 ms 14732 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14468 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14796 KB Output is correct
6 Incorrect 10 ms 14732 KB Output isn't correct
7 Halted 0 ms 0 KB -