oj.uz

Submission #172056

# Submission time Handle Problem Language Result Execution time Memory
172056 2019-12-31T02:50:03 Z AngusRitossa New Home (APIO18_new_home) C++14
47 / 100
 4964 ms 934140 KB 
#include <bits/stdc++.h>
using namespace std;
#define MXN 60010
#define MXNODES MXN*80
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
set<pair<int, int> > segments[MXNODES][2];
int l[MXNODES], r[MXNODES], upto;
void addsegment(int s, int e, pair<int, int> val, int whichone, int curr = 1, int cstart = 0, int cend = 1e8)
{
	if (e < cstart || s > cend) return;
	if (s <= cstart && cend <= e)
	{
		segments[curr][whichone].insert(val);
		return;
	}
	int mid = (cstart+cend)/2;
	if (e <= mid) 
	{
		if (!l[curr]) l[curr] = ++upto;
		addsegment(s, e, val, whichone, l[curr], cstart, mid);
	}
	else if (s > mid)
	{
		if (!r[curr]) r[curr] = ++upto;
		addsegment(s, e, val, whichone, r[curr], mid+1, cend);
	}
	else
	{
		if (!l[curr]) l[curr] = ++upto;
		if (!r[curr]) r[curr] = ++upto;
		addsegment(s, e, val, whichone, l[curr], cstart, mid);
		addsegment(s, e, val, whichone, r[curr], mid+1, cend);
	}
}
void removesegment(int s, int e, pair<int, int> val, int whichone, int curr = 1, int cstart = 0, int cend = 1e8)
{
	if (e < cstart || s > cend) return;
	if (s <= cstart && cend <= e)
	{
		segments[curr][whichone].erase(val);
		return;
	}
	int mid = (cstart+cend)/2;
	if (e <= mid) 
	{
		removesegment(s, e, val, whichone, l[curr], cstart, mid);
	}
	else if (s > mid)
	{
		removesegment(s, e, val, whichone, r[curr], mid+1, cend);
	}
	else
	{
		removesegment(s, e, val, whichone, l[curr], cstart, mid);
		removesegment(s, e, val, whichone, r[curr], mid+1, cend);
	}
}
pair<int, int> query(int node, int curr = 1, int cstart = 0, int cend = 1e8)
{
	pair<int, int> ans = { 2e8, -2e8 };
	if (segments[curr][0].size()) ans.first = segments[curr][0].begin()->first;
	if (segments[curr][1].size()) ans.second = segments[curr][1].rbegin()->first;
	if (cstart == cend) return ans;
	int mid = (cstart+cend)/2;
	pair<int, int> child;
	if (node <= mid) child = query(node, l[curr], cstart, mid);
	else child = query(node, r[curr], mid+1, cend);
	ans.first = min(ans.first, child.first);
	ans.second = max(ans.second, child.second);
	return ans;
}
int n, k, q, x[MXN], t[MXN], a[MXN], b[MXN], amwithshop;
vector<pair<int, int> > events;
set<pair<int, int> > shops[MXN]; 
pair<int, int> queries[MXN];
int sq[MXN], ans[MXN];
int doQuery(int loc)
{
	if (amwithshop != k)
	{
		return -1;
	}
	// jdi
	auto res = query(loc);
	D("%d %d\n", res.first, res.second);
	int before = loc-res.first;
	int after = res.second-loc;
	int ans = max(before, after);
	return ans;
}
int main()
{
	++upto;
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 1; i <= k; i++) 
	{
		shops[i].insert({ -2e8, -1 }), shops[i].insert({ 2e8, -2 });
		// dumbie stuff
		addsegment(-2e8, 0, {-2e8, -1}, 0);
		addsegment(0, 2e8, {2e8, -2}, 1);
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
		events.emplace_back(i, 0);
		events.emplace_back(i, 1);
	}
	for (int i = 0; i < q; i++)
	{
		scanf("%d%d", &queries[i].second, &queries[i].first);
	}
	iota(sq, sq+q, 0);
	sort(sq, sq+q, [&](int a, int b) { return queries[a].first < queries[b].first;});
	int qupto = 0;

	sort(events.begin(), events.end(), [](const pair<int, int> &i, const pair<int, int> &j)
	{
		int val1 = i.second ? b[i.first] : a[i.first];
		int val2 = j.second ? b[j.first] : a[j.first];
		return make_pair(val1, i.second) < make_pair(val2, j.second);
	});
	for (auto f : events)
	{
		int i = f.first;
		int eventType = f.second;
		int timeOfEvent = eventType ? b[i]+1 : a[i];
		while (qupto < q && queries[sq[qupto]].first < timeOfEvent)
		{
			// do query
			ans[sq[qupto]] = doQuery(queries[sq[qupto]].second);
			qupto++;
		}
		D("\nprocessing %d %d : %d (time: %d)\n", i, eventType, t[i], eventType ? b[i] : a[i]);
		if (!eventType) // new thing
		{
			D("new thing\n");
			if (shops[t[i]].size() == 2) amwithshop++;
			auto it = shops[t[i]].lower_bound({x[i], i});
			auto after = *it;
			auto before = *prev(it);
			// remove the ranges 
			int mid = (before.first+after.first)/2;
			removesegment(before.first, mid, before, 0);
			mid = (before.first+after.first+1)/2;
			removesegment(mid, after.first, after, 1);
			// add in, then add ranges (4)
			shops[t[i]].insert({x[i], i});
			mid = (before.first+x[i])/2;
			D("adding range first %d %d\n", before.first, mid);
			addsegment(before.first, mid, before, 0);
			mid = (before.first+x[i]+1)/2;
			D("adding range second %d %d\n", mid, x[i]);
			addsegment(mid, x[i], { x[i], i }, 1);
			mid = (x[i]+after.first)/2;
			D("adding range first %d %d\n", x[i], mid);
			addsegment(x[i], mid, { x[i], i }, 0);
			mid = (x[i]+after.first+1)/2;
			D("adding range second %d %d\n", mid, after.first);
			addsegment(mid, after.first, after, 1);
		}
		else // end of thing
		{
			D("end of thing\n");
			shops[t[i]].erase({x[i], i});
			auto it = shops[t[i]].lower_bound({x[i], i});
			auto after = *it;
			auto before = *prev(it);
			// remove ranges
			int mid = (before.first+x[i])/2;
			removesegment(before.first, mid, before, 0);
			mid = (before.first+x[i]+1)/2;
			removesegment(mid, x[i], { x[i], i }, 1);
			mid = (x[i]+after.first)/2;
			removesegment(x[i], mid, { x[i], i }, 0);
			mid = (x[i]+after.first+1)/2;
			removesegment(mid, after.first, after, 1);

			// add new ranges
			mid = (before.first+after.first)/2;
			addsegment(before.first, mid, before, 0);
			mid = (before.first+after.first+1)/2;
			addsegment(mid, after.first, after, 1);
			if (shops[t[i]].size() == 2) amwithshop--;
		}
	}
	while (qupto < q)
	{
		ans[sq[qupto]] = doQuery(queries[sq[qupto]].second);
		qupto++;
	}
	for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &queries[i].second, &queries[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 454200 KB Output is correct
2 Correct 418 ms 454264 KB Output is correct
3 Correct 414 ms 454160 KB Output is correct
4 Correct 414 ms 454136 KB Output is correct
5 Correct 490 ms 454284 KB Output is correct
6 Correct 428 ms 454812 KB Output is correct
7 Correct 424 ms 454496 KB Output is correct
8 Correct 425 ms 455032 KB Output is correct
9 Correct 421 ms 454776 KB Output is correct
10 Correct 426 ms 455300 KB Output is correct
11 Correct 425 ms 454404 KB Output is correct
12 Correct 466 ms 454648 KB Output is correct
13 Correct 420 ms 454264 KB Output is correct
14 Correct 422 ms 454392 KB Output is correct
15 Correct 420 ms 454524 KB Output is correct
16 Correct 461 ms 454704 KB Output is correct
17 Correct 425 ms 454500 KB Output is correct
18 Correct 427 ms 454756 KB Output is correct
19 Correct 418 ms 454816 KB Output is correct
20 Correct 426 ms 454748 KB Output is correct
21 Correct 417 ms 454264 KB Output is correct
22 Correct 418 ms 454904 KB Output is correct
23 Correct 424 ms 454908 KB Output is correct
24 Correct 444 ms 454836 KB Output is correct
25 Correct 448 ms 454648 KB Output is correct
26 Correct 504 ms 454472 KB Output is correct
27 Correct 428 ms 454392 KB Output is correct
28 Correct 417 ms 454432 KB Output is correct
29 Correct 421 ms 454376 KB Output is correct
30 Correct 422 ms 454264 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 454200 KB Output is correct
2 Correct 418 ms 454264 KB Output is correct
3 Correct 414 ms 454160 KB Output is correct
4 Correct 414 ms 454136 KB Output is correct
5 Correct 490 ms 454284 KB Output is correct
6 Correct 428 ms 454812 KB Output is correct
7 Correct 424 ms 454496 KB Output is correct
8 Correct 425 ms 455032 KB Output is correct
9 Correct 421 ms 454776 KB Output is correct
10 Correct 426 ms 455300 KB Output is correct
11 Correct 425 ms 454404 KB Output is correct
12 Correct 466 ms 454648 KB Output is correct
13 Correct 420 ms 454264 KB Output is correct
14 Correct 422 ms 454392 KB Output is correct
15 Correct 420 ms 454524 KB Output is correct
16 Correct 461 ms 454704 KB Output is correct
17 Correct 425 ms 454500 KB Output is correct
18 Correct 427 ms 454756 KB Output is correct
19 Correct 418 ms 454816 KB Output is correct
20 Correct 426 ms 454748 KB Output is correct
21 Correct 417 ms 454264 KB Output is correct
22 Correct 418 ms 454904 KB Output is correct
23 Correct 424 ms 454908 KB Output is correct
24 Correct 444 ms 454836 KB Output is correct
25 Correct 448 ms 454648 KB Output is correct
26 Correct 504 ms 454472 KB Output is correct
27 Correct 428 ms 454392 KB Output is correct
28 Correct 417 ms 454432 KB Output is correct
29 Correct 421 ms 454376 KB Output is correct
30 Correct 422 ms 454264 KB Output is correct
31 Correct 4892 ms 586860 KB Output is correct
32 Correct 799 ms 461564 KB Output is correct
33 Correct 2983 ms 518184 KB Output is correct
34 Correct 4964 ms 527936 KB Output is correct
35 Correct 4599 ms 581660 KB Output is correct
36 Correct 3103 ms 561704 KB Output is correct
37 Correct 3009 ms 494756 KB Output is correct
38 Correct 2228 ms 493780 KB Output is correct
39 Correct 1517 ms 488552 KB Output is correct
40 Correct 1541 ms 489272 KB Output is correct
41 Correct 2130 ms 480300 KB Output is correct
42 Correct 2237 ms 480440 KB Output is correct
43 Correct 747 ms 468280 KB Output is correct
44 Correct 2140 ms 480036 KB Output is correct
45 Correct 1794 ms 479548 KB Output is correct
46 Correct 1580 ms 479412 KB Output is correct
47 Correct 1004 ms 476480 KB Output is correct
48 Correct 948 ms 477032 KB Output is correct
49 Correct 1175 ms 478320 KB Output is correct
50 Correct 1546 ms 478716 KB Output is correct
51 Correct 1176 ms 478500 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1083 ms 934140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1117 ms 929424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 454200 KB Output is correct
2 Correct 418 ms 454264 KB Output is correct
3 Correct 414 ms 454160 KB Output is correct
4 Correct 414 ms 454136 KB Output is correct
5 Correct 490 ms 454284 KB Output is correct
6 Correct 428 ms 454812 KB Output is correct
7 Correct 424 ms 454496 KB Output is correct
8 Correct 425 ms 455032 KB Output is correct
9 Correct 421 ms 454776 KB Output is correct
10 Correct 426 ms 455300 KB Output is correct
11 Correct 425 ms 454404 KB Output is correct
12 Correct 466 ms 454648 KB Output is correct
13 Correct 420 ms 454264 KB Output is correct
14 Correct 422 ms 454392 KB Output is correct
15 Correct 420 ms 454524 KB Output is correct
16 Correct 461 ms 454704 KB Output is correct
17 Correct 425 ms 454500 KB Output is correct
18 Correct 427 ms 454756 KB Output is correct
19 Correct 418 ms 454816 KB Output is correct
20 Correct 426 ms 454748 KB Output is correct
21 Correct 417 ms 454264 KB Output is correct
22 Correct 418 ms 454904 KB Output is correct
23 Correct 424 ms 454908 KB Output is correct
24 Correct 444 ms 454836 KB Output is correct
25 Correct 448 ms 454648 KB Output is correct
26 Correct 504 ms 454472 KB Output is correct
27 Correct 428 ms 454392 KB Output is correct
28 Correct 417 ms 454432 KB Output is correct
29 Correct 421 ms 454376 KB Output is correct
30 Correct 422 ms 454264 KB Output is correct
31 Correct 4892 ms 586860 KB Output is correct
32 Correct 799 ms 461564 KB Output is correct
33 Correct 2983 ms 518184 KB Output is correct
34 Correct 4964 ms 527936 KB Output is correct
35 Correct 4599 ms 581660 KB Output is correct
36 Correct 3103 ms 561704 KB Output is correct
37 Correct 3009 ms 494756 KB Output is correct
38 Correct 2228 ms 493780 KB Output is correct
39 Correct 1517 ms 488552 KB Output is correct
40 Correct 1541 ms 489272 KB Output is correct
41 Correct 2130 ms 480300 KB Output is correct
42 Correct 2237 ms 480440 KB Output is correct
43 Correct 747 ms 468280 KB Output is correct
44 Correct 2140 ms 480036 KB Output is correct
45 Correct 1794 ms 479548 KB Output is correct
46 Correct 1580 ms 479412 KB Output is correct
47 Correct 1004 ms 476480 KB Output is correct
48 Correct 948 ms 477032 KB Output is correct
49 Correct 1175 ms 478320 KB Output is correct
50 Correct 1546 ms 478716 KB Output is correct
51 Correct 1176 ms 478500 KB Output is correct
52 Correct 1837 ms 553064 KB Output is correct
53 Correct 1665 ms 504140 KB Output is correct
54 Correct 3956 ms 590256 KB Output is correct
55 Correct 2251 ms 504716 KB Output is correct
56 Correct 2548 ms 517016 KB Output is correct
57 Correct 2346 ms 487780 KB Output is correct
58 Correct 2408 ms 505072 KB Output is correct
59 Correct 2291 ms 517112 KB Output is correct
60 Correct 2476 ms 487856 KB Output is correct
61 Correct 591 ms 473972 KB Output is correct
62 Correct 1997 ms 553324 KB Output is correct
63 Correct 3672 ms 559464 KB Output is correct
64 Correct 3545 ms 547404 KB Output is correct
65 Correct 3754 ms 502460 KB Output is correct
66 Correct 2641 ms 481772 KB Output is correct
67 Correct 1865 ms 469008 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 454200 KB Output is correct
2 Correct 418 ms 454264 KB Output is correct
3 Correct 414 ms 454160 KB Output is correct
4 Correct 414 ms 454136 KB Output is correct
5 Correct 490 ms 454284 KB Output is correct
6 Correct 428 ms 454812 KB Output is correct
7 Correct 424 ms 454496 KB Output is correct
8 Correct 425 ms 455032 KB Output is correct
9 Correct 421 ms 454776 KB Output is correct
10 Correct 426 ms 455300 KB Output is correct
11 Correct 425 ms 454404 KB Output is correct
12 Correct 466 ms 454648 KB Output is correct
13 Correct 420 ms 454264 KB Output is correct
14 Correct 422 ms 454392 KB Output is correct
15 Correct 420 ms 454524 KB Output is correct
16 Correct 461 ms 454704 KB Output is correct
17 Correct 425 ms 454500 KB Output is correct
18 Correct 427 ms 454756 KB Output is correct
19 Correct 418 ms 454816 KB Output is correct
20 Correct 426 ms 454748 KB Output is correct
21 Correct 417 ms 454264 KB Output is correct
22 Correct 418 ms 454904 KB Output is correct
23 Correct 424 ms 454908 KB Output is correct
24 Correct 444 ms 454836 KB Output is correct
25 Correct 448 ms 454648 KB Output is correct
26 Correct 504 ms 454472 KB Output is correct
27 Correct 428 ms 454392 KB Output is correct
28 Correct 417 ms 454432 KB Output is correct
29 Correct 421 ms 454376 KB Output is correct
30 Correct 422 ms 454264 KB Output is correct
31 Correct 4892 ms 586860 KB Output is correct
32 Correct 799 ms 461564 KB Output is correct
33 Correct 2983 ms 518184 KB Output is correct
34 Correct 4964 ms 527936 KB Output is correct
35 Correct 4599 ms 581660 KB Output is correct
36 Correct 3103 ms 561704 KB Output is correct
37 Correct 3009 ms 494756 KB Output is correct
38 Correct 2228 ms 493780 KB Output is correct
39 Correct 1517 ms 488552 KB Output is correct
40 Correct 1541 ms 489272 KB Output is correct
41 Correct 2130 ms 480300 KB Output is correct
42 Correct 2237 ms 480440 KB Output is correct
43 Correct 747 ms 468280 KB Output is correct
44 Correct 2140 ms 480036 KB Output is correct
45 Correct 1794 ms 479548 KB Output is correct
46 Correct 1580 ms 479412 KB Output is correct
47 Correct 1004 ms 476480 KB Output is correct
48 Correct 948 ms 477032 KB Output is correct
49 Correct 1175 ms 478320 KB Output is correct
50 Correct 1546 ms 478716 KB Output is correct
51 Correct 1176 ms 478500 KB Output is correct
52 Runtime error 1083 ms 934140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -