답안 #469855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469855	2021-09-02T06:32:17 Z	flappybird	새 집 (APIO18_new_home)	C++14	80 / 100	5000 ms	413352 KB

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 long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 10000000000001
#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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14436 KB	Output is correct
3	Correct	10 ms	14412 KB	Output is correct
4	Correct	9 ms	14412 KB	Output is correct
5	Correct	11 ms	14984 KB	Output is correct
6	Correct	12 ms	14992 KB	Output is correct
7	Correct	12 ms	15036 KB	Output is correct
8	Correct	11 ms	15104 KB	Output is correct
9	Correct	12 ms	15124 KB	Output is correct
10	Correct	12 ms	15052 KB	Output is correct
11	Correct	11 ms	15052 KB	Output is correct
12	Correct	12 ms	14996 KB	Output is correct
13	Correct	11 ms	15068 KB	Output is correct
14	Correct	12 ms	14992 KB	Output is correct
15	Correct	12 ms	15052 KB	Output is correct
16	Correct	12 ms	14992 KB	Output is correct
17	Correct	12 ms	15036 KB	Output is correct
18	Correct	12 ms	15052 KB	Output is correct
19	Correct	12 ms	15052 KB	Output is correct
20	Correct	12 ms	14992 KB	Output is correct
21	Correct	11 ms	14992 KB	Output is correct
22	Correct	11 ms	15100 KB	Output is correct
23	Correct	11 ms	15052 KB	Output is correct
24	Correct	11 ms	15116 KB	Output is correct
25	Correct	12 ms	15052 KB	Output is correct
26	Correct	12 ms	15052 KB	Output is correct
27	Correct	11 ms	14924 KB	Output is correct
28	Correct	12 ms	15052 KB	Output is correct
29	Correct	12 ms	15052 KB	Output is correct
30	Correct	11 ms	14784 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14436 KB	Output is correct
3	Correct	10 ms	14412 KB	Output is correct
4	Correct	9 ms	14412 KB	Output is correct
5	Correct	11 ms	14984 KB	Output is correct
6	Correct	12 ms	14992 KB	Output is correct
7	Correct	12 ms	15036 KB	Output is correct
8	Correct	11 ms	15104 KB	Output is correct
9	Correct	12 ms	15124 KB	Output is correct
10	Correct	12 ms	15052 KB	Output is correct
11	Correct	11 ms	15052 KB	Output is correct
12	Correct	12 ms	14996 KB	Output is correct
13	Correct	11 ms	15068 KB	Output is correct
14	Correct	12 ms	14992 KB	Output is correct
15	Correct	12 ms	15052 KB	Output is correct
16	Correct	12 ms	14992 KB	Output is correct
17	Correct	12 ms	15036 KB	Output is correct
18	Correct	12 ms	15052 KB	Output is correct
19	Correct	12 ms	15052 KB	Output is correct
20	Correct	12 ms	14992 KB	Output is correct
21	Correct	11 ms	14992 KB	Output is correct
22	Correct	11 ms	15100 KB	Output is correct
23	Correct	11 ms	15052 KB	Output is correct
24	Correct	11 ms	15116 KB	Output is correct
25	Correct	12 ms	15052 KB	Output is correct
26	Correct	12 ms	15052 KB	Output is correct
27	Correct	11 ms	14924 KB	Output is correct
28	Correct	12 ms	15052 KB	Output is correct
29	Correct	12 ms	15052 KB	Output is correct
30	Correct	11 ms	14784 KB	Output is correct
31	Correct	785 ms	96468 KB	Output is correct
32	Correct	304 ms	82172 KB	Output is correct
33	Correct	819 ms	94672 KB	Output is correct
34	Correct	775 ms	94912 KB	Output is correct
35	Correct	801 ms	96496 KB	Output is correct
36	Correct	882 ms	96348 KB	Output is correct
37	Correct	551 ms	93752 KB	Output is correct
38	Correct	572 ms	93600 KB	Output is correct
39	Correct	468 ms	93472 KB	Output is correct
40	Correct	495 ms	93480 KB	Output is correct
41	Correct	668 ms	93648 KB	Output is correct
42	Correct	593 ms	93580 KB	Output is correct
43	Correct	236 ms	84840 KB	Output is correct
44	Correct	630 ms	93792 KB	Output is correct
45	Correct	626 ms	93692 KB	Output is correct
46	Correct	569 ms	93688 KB	Output is correct
47	Correct	382 ms	91856 KB	Output is correct
48	Correct	368 ms	91488 KB	Output is correct
49	Correct	408 ms	92372 KB	Output is correct
50	Correct	414 ms	93196 KB	Output is correct
51	Correct	407 ms	92224 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2933 ms	318932 KB	Output is correct
2	Correct	3246 ms	324224 KB	Output is correct
3	Correct	2465 ms	357228 KB	Output is correct
4	Correct	2866 ms	336772 KB	Output is correct
5	Correct	3092 ms	323772 KB	Output is correct
6	Correct	3099 ms	324272 KB	Output is correct
7	Correct	1831 ms	357280 KB	Output is correct
8	Correct	2247 ms	336728 KB	Output is correct
9	Correct	2319 ms	329516 KB	Output is correct
10	Correct	2649 ms	325320 KB	Output is correct
11	Correct	1665 ms	321812 KB	Output is correct
12	Correct	1764 ms	324428 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4643 ms	341208 KB	Output is correct
2	Correct	1667 ms	315548 KB	Output is correct
3	Correct	4803 ms	352196 KB	Output is correct
4	Correct	3925 ms	383384 KB	Output is correct
5	Correct	3791 ms	358628 KB	Output is correct
6	Correct	3694 ms	362616 KB	Output is correct
7	Correct	4643 ms	351652 KB	Output is correct
8	Correct	4767 ms	352036 KB	Output is correct
9	Correct	3503 ms	384360 KB	Output is correct
10	Correct	3877 ms	361496 KB	Output is correct
11	Correct	4254 ms	355456 KB	Output is correct
12	Correct	4419 ms	352988 KB	Output is correct
13	Correct	2177 ms	346260 KB	Output is correct
14	Correct	2121 ms	344028 KB	Output is correct
15	Correct	2327 ms	348632 KB	Output is correct
16	Correct	2500 ms	351468 KB	Output is correct
17	Correct	2505 ms	347612 KB	Output is correct

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14436 KB	Output is correct
3	Correct	10 ms	14412 KB	Output is correct
4	Correct	9 ms	14412 KB	Output is correct
5	Correct	11 ms	14984 KB	Output is correct
6	Correct	12 ms	14992 KB	Output is correct
7	Correct	12 ms	15036 KB	Output is correct
8	Correct	11 ms	15104 KB	Output is correct
9	Correct	12 ms	15124 KB	Output is correct
10	Correct	12 ms	15052 KB	Output is correct
11	Correct	11 ms	15052 KB	Output is correct
12	Correct	12 ms	14996 KB	Output is correct
13	Correct	11 ms	15068 KB	Output is correct
14	Correct	12 ms	14992 KB	Output is correct
15	Correct	12 ms	15052 KB	Output is correct
16	Correct	12 ms	14992 KB	Output is correct
17	Correct	12 ms	15036 KB	Output is correct
18	Correct	12 ms	15052 KB	Output is correct
19	Correct	12 ms	15052 KB	Output is correct
20	Correct	12 ms	14992 KB	Output is correct
21	Correct	11 ms	14992 KB	Output is correct
22	Correct	11 ms	15100 KB	Output is correct
23	Correct	11 ms	15052 KB	Output is correct
24	Correct	11 ms	15116 KB	Output is correct
25	Correct	12 ms	15052 KB	Output is correct
26	Correct	12 ms	15052 KB	Output is correct
27	Correct	11 ms	14924 KB	Output is correct
28	Correct	12 ms	15052 KB	Output is correct
29	Correct	12 ms	15052 KB	Output is correct
30	Correct	11 ms	14784 KB	Output is correct
31	Correct	785 ms	96468 KB	Output is correct
32	Correct	304 ms	82172 KB	Output is correct
33	Correct	819 ms	94672 KB	Output is correct
34	Correct	775 ms	94912 KB	Output is correct
35	Correct	801 ms	96496 KB	Output is correct
36	Correct	882 ms	96348 KB	Output is correct
37	Correct	551 ms	93752 KB	Output is correct
38	Correct	572 ms	93600 KB	Output is correct
39	Correct	468 ms	93472 KB	Output is correct
40	Correct	495 ms	93480 KB	Output is correct
41	Correct	668 ms	93648 KB	Output is correct
42	Correct	593 ms	93580 KB	Output is correct
43	Correct	236 ms	84840 KB	Output is correct
44	Correct	630 ms	93792 KB	Output is correct
45	Correct	626 ms	93692 KB	Output is correct
46	Correct	569 ms	93688 KB	Output is correct
47	Correct	382 ms	91856 KB	Output is correct
48	Correct	368 ms	91488 KB	Output is correct
49	Correct	408 ms	92372 KB	Output is correct
50	Correct	414 ms	93196 KB	Output is correct
51	Correct	407 ms	92224 KB	Output is correct
52	Correct	675 ms	102508 KB	Output is correct
53	Correct	642 ms	100652 KB	Output is correct
54	Correct	633 ms	98292 KB	Output is correct
55	Correct	610 ms	96772 KB	Output is correct
56	Correct	628 ms	98060 KB	Output is correct
57	Correct	617 ms	94624 KB	Output is correct
58	Correct	600 ms	96756 KB	Output is correct
59	Correct	617 ms	98120 KB	Output is correct
60	Correct	608 ms	94620 KB	Output is correct
61	Correct	259 ms	90900 KB	Output is correct
62	Correct	661 ms	102512 KB	Output is correct
63	Correct	665 ms	99004 KB	Output is correct
64	Correct	670 ms	97508 KB	Output is correct
65	Correct	671 ms	94996 KB	Output is correct
66	Correct	625 ms	93848 KB	Output is correct
67	Correct	441 ms	82200 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14436 KB	Output is correct
3	Correct	10 ms	14412 KB	Output is correct
4	Correct	9 ms	14412 KB	Output is correct
5	Correct	11 ms	14984 KB	Output is correct
6	Correct	12 ms	14992 KB	Output is correct
7	Correct	12 ms	15036 KB	Output is correct
8	Correct	11 ms	15104 KB	Output is correct
9	Correct	12 ms	15124 KB	Output is correct
10	Correct	12 ms	15052 KB	Output is correct
11	Correct	11 ms	15052 KB	Output is correct
12	Correct	12 ms	14996 KB	Output is correct
13	Correct	11 ms	15068 KB	Output is correct
14	Correct	12 ms	14992 KB	Output is correct
15	Correct	12 ms	15052 KB	Output is correct
16	Correct	12 ms	14992 KB	Output is correct
17	Correct	12 ms	15036 KB	Output is correct
18	Correct	12 ms	15052 KB	Output is correct
19	Correct	12 ms	15052 KB	Output is correct
20	Correct	12 ms	14992 KB	Output is correct
21	Correct	11 ms	14992 KB	Output is correct
22	Correct	11 ms	15100 KB	Output is correct
23	Correct	11 ms	15052 KB	Output is correct
24	Correct	11 ms	15116 KB	Output is correct
25	Correct	12 ms	15052 KB	Output is correct
26	Correct	12 ms	15052 KB	Output is correct
27	Correct	11 ms	14924 KB	Output is correct
28	Correct	12 ms	15052 KB	Output is correct
29	Correct	12 ms	15052 KB	Output is correct
30	Correct	11 ms	14784 KB	Output is correct
31	Correct	785 ms	96468 KB	Output is correct
32	Correct	304 ms	82172 KB	Output is correct
33	Correct	819 ms	94672 KB	Output is correct
34	Correct	775 ms	94912 KB	Output is correct
35	Correct	801 ms	96496 KB	Output is correct
36	Correct	882 ms	96348 KB	Output is correct
37	Correct	551 ms	93752 KB	Output is correct
38	Correct	572 ms	93600 KB	Output is correct
39	Correct	468 ms	93472 KB	Output is correct
40	Correct	495 ms	93480 KB	Output is correct
41	Correct	668 ms	93648 KB	Output is correct
42	Correct	593 ms	93580 KB	Output is correct
43	Correct	236 ms	84840 KB	Output is correct
44	Correct	630 ms	93792 KB	Output is correct
45	Correct	626 ms	93692 KB	Output is correct
46	Correct	569 ms	93688 KB	Output is correct
47	Correct	382 ms	91856 KB	Output is correct
48	Correct	368 ms	91488 KB	Output is correct
49	Correct	408 ms	92372 KB	Output is correct
50	Correct	414 ms	93196 KB	Output is correct
51	Correct	407 ms	92224 KB	Output is correct
52	Correct	2933 ms	318932 KB	Output is correct
53	Correct	3246 ms	324224 KB	Output is correct
54	Correct	2465 ms	357228 KB	Output is correct
55	Correct	2866 ms	336772 KB	Output is correct
56	Correct	3092 ms	323772 KB	Output is correct
57	Correct	3099 ms	324272 KB	Output is correct
58	Correct	1831 ms	357280 KB	Output is correct
59	Correct	2247 ms	336728 KB	Output is correct
60	Correct	2319 ms	329516 KB	Output is correct
61	Correct	2649 ms	325320 KB	Output is correct
62	Correct	1665 ms	321812 KB	Output is correct
63	Correct	1764 ms	324428 KB	Output is correct
64	Correct	4643 ms	341208 KB	Output is correct
65	Correct	1667 ms	315548 KB	Output is correct
66	Correct	4803 ms	352196 KB	Output is correct
67	Correct	3925 ms	383384 KB	Output is correct
68	Correct	3791 ms	358628 KB	Output is correct
69	Correct	3694 ms	362616 KB	Output is correct
70	Correct	4643 ms	351652 KB	Output is correct
71	Correct	4767 ms	352036 KB	Output is correct
72	Correct	3503 ms	384360 KB	Output is correct
73	Correct	3877 ms	361496 KB	Output is correct
74	Correct	4254 ms	355456 KB	Output is correct
75	Correct	4419 ms	352988 KB	Output is correct
76	Correct	2177 ms	346260 KB	Output is correct
77	Correct	2121 ms	344028 KB	Output is correct
78	Correct	2327 ms	348632 KB	Output is correct
79	Correct	2500 ms	351468 KB	Output is correct
80	Correct	2505 ms	347612 KB	Output is correct
81	Correct	675 ms	102508 KB	Output is correct
82	Correct	642 ms	100652 KB	Output is correct
83	Correct	633 ms	98292 KB	Output is correct
84	Correct	610 ms	96772 KB	Output is correct
85	Correct	628 ms	98060 KB	Output is correct
86	Correct	617 ms	94624 KB	Output is correct
87	Correct	600 ms	96756 KB	Output is correct
88	Correct	617 ms	98120 KB	Output is correct
89	Correct	608 ms	94620 KB	Output is correct
90	Correct	259 ms	90900 KB	Output is correct
91	Correct	661 ms	102512 KB	Output is correct
92	Correct	665 ms	99004 KB	Output is correct
93	Correct	670 ms	97508 KB	Output is correct
94	Correct	671 ms	94996 KB	Output is correct
95	Correct	625 ms	93848 KB	Output is correct
96	Correct	441 ms	82200 KB	Output is correct
97	Correct	4472 ms	413352 KB	Output is correct
98	Correct	1669 ms	311708 KB	Output is correct
99	Execution timed out	5051 ms	371676 KB	Time limit exceeded
100	Halted	0 ms	0 KB	-

답안 #469855

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 23.0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
23.0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0