Submission #48866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48866	2018-05-19T11:09:44 Z	kriii	New Home (APIO18_new_home)	C++17	57 / 100	5000 ms	249844 KB

new_home

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
using namespace std;

int N,K,Q;
int C,XP[1001001];

struct query{
	int y,o,x,t;
	bool operator <(const query &t)const{
		if (y == t.y) return o < t.o;
		return y < t.y;
	};
}qs[900900]; int qc;

map<int, int> make[300300];
int ans[300300];

const int non = 500000000;
const int Z = 1<<20;
multiset<int> upc[Z];
multiset<int, greater<int> > downc[Z];
int up[Z*2],down[Z*2];

void push(int v, int u, int d, bool in)
{
	int x = lower_bound(XP, XP+C, v) - XP;

	if (in) upc[x].insert(u);
	else upc[x].erase(upc[x].find(u));
	if (upc[x].empty()) up[x+Z] = non;
	else up[x+Z] = *upc[x].begin();

	if (in) downc[x].insert(d);
	else downc[x].erase(downc[x].find(d));
	if (downc[x].empty()) down[x+Z] = -non;
	else down[x+Z] = *downc[x].begin();

	x = (x + Z) / 2;
	while (x){
		up[x] = min(up[x*2], up[x*2+1]);
		down[x] = max(down[x*2], down[x*2+1]);
		x /= 2;
	}
}

int out(int v)
{
	int u = non, d = -non, p = lower_bound(XP,XP+C,v) - XP;
	{
		int x = p + Z, y = C-1 + Z;
		while (x < y){
			if (x & 1) u = min(u, up[x++]);
			if (~y & 1) u = min(u, up[y--]);
			x /= 2; y /= 2;
		}
		if (x == y) u = min(u, up[x]);
	}
	{
		int x = Z, y = p + Z - 1;
		while (x < y){
			if (x & 1) d = max(d, down[x++]);
			if (~y & 1) d = max(d, down[y--]);
			x /= 2; y /= 2;
		}
		if (x == y) d = max(d, down[x]);
	}

	return max(v-u,-v+d);
}

void mt(int s, int e, bool in)
{
	push((s+e)/2,s,e,in);
}

int main()
{
	scanf ("%d %d %d",&N,&K,&Q);
	for (int i=0;i<N;i++){
		int x,t,a,b; scanf ("%d %d %d %d",&x,&t,&a,&b);
		x *= 2;
		qs[qc++] = {a,0,x,t};
		qs[qc++] = {b+1,0,x,-t};
	}
	for (int i=0;i<Q;i++){
		int l,y; scanf ("%d %d",&l,&y);
		l *= 2;
		qs[qc++] = {y,1,l,i};
	}
	sort(qs,qs+qc);

	for (int i=1;i<=K;i++){
		make[i][-non] = make[i][non] = 1;
	}
	XP[C++] = -non;
	XP[C++] = non;
	XP[C++] = 0;

	for (int i=0;i<qc;i++){
		auto &q = qs[i];
		if (q.o == 0){
			int x = q.x, t = q.t;
			if (t > 0){
				int &c = make[t][x];
				if (c == 0){
					auto I = make[t].find(x);
					auto J = I, K = I; J--; K++;
					XP[C++] = (J->first + I->first) / 2;
					XP[C++] = (I->first + K->first) / 2;
				}
				c++;
			}
			else{
				t = -t;
				int &c = make[t][x];
				if (c == 1){
					auto I = make[t].find(x);
					auto J = I, K = I; J--; K++;
					XP[C++] = (J->first + K->first) / 2;
					make[t].erase(I);
				}
				else c--;
			}
		}
	}

	sort(XP,XP+C);
	C = unique(XP,XP+C) - XP;

	int v = lower_bound(XP,XP+C,0) - XP;
	for (int i=1;i<K;i++){
		upc[v].insert(-non);
		downc[v].insert(non);
	}
	mt(-non,non,true);

	for (int i=1;i<Z*2;i++) up[i] = non, down[i] = -non;

	int have = 0;
	for (int i=0;i<qc;i++){
		auto &q = qs[i];
		if (q.o == 0){
			int x = q.x, t = q.t;
			if (t > 0){
				if (make[t].size() == 2) have++;
				int &c = make[t][x];
				if (c == 0){
					auto I = make[t].find(x);
					auto J = I, K = I; J--; K++;
					mt(J->first,K->first,false);
					mt(J->first,I->first,true);
					mt(I->first,K->first,true);
				}
				c++;
			}
			else{
				t = -t;
				int &c = make[t][x];
				if (c == 1){
					auto I = make[t].find(x);
					auto J = I, K = I; J--; K++;
					mt(J->first,I->first,false);
					mt(I->first,K->first,false);
					mt(J->first,K->first,true);
					make[t].erase(I);
					if (make[t].size() == 2) have--;
				}
				else c--;
			}
		}
		else{
			ans[q.t] = have == K ? out(q.x) / 2 : -1;
		}
	}

	for (int i=0;i<Q;i++){
		printf ("%d\n",ans[i]);
	}

	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:83:8: 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:85:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x,t,a,b; scanf ("%d %d %d %d",&x,&t,&a,&b);
                ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int l,y; scanf ("%d %d",&l,&y);
            ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	129468 KB	Output is correct
2	Correct	114 ms	129476 KB	Output is correct
3	Correct	139 ms	129476 KB	Output is correct
4	Correct	113 ms	129516 KB	Output is correct
5	Correct	112 ms	129664 KB	Output is correct
6	Correct	112 ms	129852 KB	Output is correct
7	Correct	130 ms	129852 KB	Output is correct
8	Correct	114 ms	129852 KB	Output is correct
9	Correct	119 ms	129852 KB	Output is correct
10	Correct	115 ms	129852 KB	Output is correct
11	Correct	115 ms	129852 KB	Output is correct
12	Correct	112 ms	129852 KB	Output is correct
13	Correct	113 ms	129852 KB	Output is correct
14	Correct	115 ms	129852 KB	Output is correct
15	Correct	115 ms	129852 KB	Output is correct
16	Correct	112 ms	129852 KB	Output is correct
17	Correct	110 ms	129852 KB	Output is correct
18	Correct	131 ms	129852 KB	Output is correct
19	Correct	115 ms	129856 KB	Output is correct
20	Correct	117 ms	129856 KB	Output is correct
21	Correct	116 ms	129856 KB	Output is correct
22	Correct	123 ms	129856 KB	Output is correct
23	Correct	115 ms	129856 KB	Output is correct
24	Correct	113 ms	129856 KB	Output is correct
25	Correct	114 ms	129856 KB	Output is correct
26	Correct	113 ms	129856 KB	Output is correct
27	Correct	106 ms	129856 KB	Output is correct
28	Correct	118 ms	129856 KB	Output is correct
29	Correct	110 ms	129856 KB	Output is correct
30	Correct	113 ms	129856 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	129468 KB	Output is correct
2	Correct	114 ms	129476 KB	Output is correct
3	Correct	139 ms	129476 KB	Output is correct
4	Correct	113 ms	129516 KB	Output is correct
5	Correct	112 ms	129664 KB	Output is correct
6	Correct	112 ms	129852 KB	Output is correct
7	Correct	130 ms	129852 KB	Output is correct
8	Correct	114 ms	129852 KB	Output is correct
9	Correct	119 ms	129852 KB	Output is correct
10	Correct	115 ms	129852 KB	Output is correct
11	Correct	115 ms	129852 KB	Output is correct
12	Correct	112 ms	129852 KB	Output is correct
13	Correct	113 ms	129852 KB	Output is correct
14	Correct	115 ms	129852 KB	Output is correct
15	Correct	115 ms	129852 KB	Output is correct
16	Correct	112 ms	129852 KB	Output is correct
17	Correct	110 ms	129852 KB	Output is correct
18	Correct	131 ms	129852 KB	Output is correct
19	Correct	115 ms	129856 KB	Output is correct
20	Correct	117 ms	129856 KB	Output is correct
21	Correct	116 ms	129856 KB	Output is correct
22	Correct	123 ms	129856 KB	Output is correct
23	Correct	115 ms	129856 KB	Output is correct
24	Correct	113 ms	129856 KB	Output is correct
25	Correct	114 ms	129856 KB	Output is correct
26	Correct	113 ms	129856 KB	Output is correct
27	Correct	106 ms	129856 KB	Output is correct
28	Correct	118 ms	129856 KB	Output is correct
29	Correct	110 ms	129856 KB	Output is correct
30	Correct	113 ms	129856 KB	Output is correct
31	Correct	752 ms	142488 KB	Output is correct
32	Correct	172 ms	142488 KB	Output is correct
33	Correct	683 ms	142488 KB	Output is correct
34	Correct	754 ms	142488 KB	Output is correct
35	Correct	833 ms	142512 KB	Output is correct
36	Correct	766 ms	142512 KB	Output is correct
37	Correct	490 ms	142512 KB	Output is correct
38	Correct	502 ms	142512 KB	Output is correct
39	Correct	361 ms	142512 KB	Output is correct
40	Correct	498 ms	142512 KB	Output is correct
41	Correct	505 ms	142512 KB	Output is correct
42	Correct	439 ms	142512 KB	Output is correct
43	Correct	183 ms	142512 KB	Output is correct
44	Correct	526 ms	142512 KB	Output is correct
45	Correct	539 ms	142512 KB	Output is correct
46	Correct	413 ms	142512 KB	Output is correct
47	Correct	295 ms	142512 KB	Output is correct
48	Correct	293 ms	142512 KB	Output is correct
49	Correct	321 ms	142512 KB	Output is correct
50	Correct	356 ms	142512 KB	Output is correct
51	Correct	370 ms	142512 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3773 ms	204740 KB	Output is correct
2	Correct	4462 ms	204740 KB	Output is correct
3	Correct	3244 ms	249836 KB	Output is correct
4	Correct	3754 ms	249836 KB	Output is correct
5	Correct	3652 ms	249836 KB	Output is correct
6	Correct	4355 ms	249836 KB	Output is correct
7	Correct	2818 ms	249844 KB	Output is correct
8	Correct	2647 ms	249844 KB	Output is correct
9	Correct	2624 ms	249844 KB	Output is correct
10	Correct	3203 ms	249844 KB	Output is correct
11	Correct	1960 ms	249844 KB	Output is correct
12	Correct	1961 ms	249844 KB	Output is correct

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4630 ms	249844 KB	Output is correct
2	Correct	429 ms	249844 KB	Output is correct
3	Execution timed out	5043 ms	249844 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	129468 KB	Output is correct
2	Correct	114 ms	129476 KB	Output is correct
3	Correct	139 ms	129476 KB	Output is correct
4	Correct	113 ms	129516 KB	Output is correct
5	Correct	112 ms	129664 KB	Output is correct
6	Correct	112 ms	129852 KB	Output is correct
7	Correct	130 ms	129852 KB	Output is correct
8	Correct	114 ms	129852 KB	Output is correct
9	Correct	119 ms	129852 KB	Output is correct
10	Correct	115 ms	129852 KB	Output is correct
11	Correct	115 ms	129852 KB	Output is correct
12	Correct	112 ms	129852 KB	Output is correct
13	Correct	113 ms	129852 KB	Output is correct
14	Correct	115 ms	129852 KB	Output is correct
15	Correct	115 ms	129852 KB	Output is correct
16	Correct	112 ms	129852 KB	Output is correct
17	Correct	110 ms	129852 KB	Output is correct
18	Correct	131 ms	129852 KB	Output is correct
19	Correct	115 ms	129856 KB	Output is correct
20	Correct	117 ms	129856 KB	Output is correct
21	Correct	116 ms	129856 KB	Output is correct
22	Correct	123 ms	129856 KB	Output is correct
23	Correct	115 ms	129856 KB	Output is correct
24	Correct	113 ms	129856 KB	Output is correct
25	Correct	114 ms	129856 KB	Output is correct
26	Correct	113 ms	129856 KB	Output is correct
27	Correct	106 ms	129856 KB	Output is correct
28	Correct	118 ms	129856 KB	Output is correct
29	Correct	110 ms	129856 KB	Output is correct
30	Correct	113 ms	129856 KB	Output is correct
31	Correct	752 ms	142488 KB	Output is correct
32	Correct	172 ms	142488 KB	Output is correct
33	Correct	683 ms	142488 KB	Output is correct
34	Correct	754 ms	142488 KB	Output is correct
35	Correct	833 ms	142512 KB	Output is correct
36	Correct	766 ms	142512 KB	Output is correct
37	Correct	490 ms	142512 KB	Output is correct
38	Correct	502 ms	142512 KB	Output is correct
39	Correct	361 ms	142512 KB	Output is correct
40	Correct	498 ms	142512 KB	Output is correct
41	Correct	505 ms	142512 KB	Output is correct
42	Correct	439 ms	142512 KB	Output is correct
43	Correct	183 ms	142512 KB	Output is correct
44	Correct	526 ms	142512 KB	Output is correct
45	Correct	539 ms	142512 KB	Output is correct
46	Correct	413 ms	142512 KB	Output is correct
47	Correct	295 ms	142512 KB	Output is correct
48	Correct	293 ms	142512 KB	Output is correct
49	Correct	321 ms	142512 KB	Output is correct
50	Correct	356 ms	142512 KB	Output is correct
51	Correct	370 ms	142512 KB	Output is correct
52	Correct	757 ms	249844 KB	Output is correct
53	Correct	614 ms	249844 KB	Output is correct
54	Correct	635 ms	249844 KB	Output is correct
55	Correct	486 ms	249844 KB	Output is correct
56	Correct	587 ms	249844 KB	Output is correct
57	Correct	683 ms	249844 KB	Output is correct
58	Correct	634 ms	249844 KB	Output is correct
59	Correct	628 ms	249844 KB	Output is correct
60	Correct	508 ms	249844 KB	Output is correct
61	Correct	419 ms	249844 KB	Output is correct
62	Correct	573 ms	249844 KB	Output is correct
63	Correct	583 ms	249844 KB	Output is correct
64	Correct	574 ms	249844 KB	Output is correct
65	Correct	577 ms	249844 KB	Output is correct
66	Correct	461 ms	249844 KB	Output is correct
67	Correct	443 ms	249844 KB	Output is correct

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	129468 KB	Output is correct
2	Correct	114 ms	129476 KB	Output is correct
3	Correct	139 ms	129476 KB	Output is correct
4	Correct	113 ms	129516 KB	Output is correct
5	Correct	112 ms	129664 KB	Output is correct
6	Correct	112 ms	129852 KB	Output is correct
7	Correct	130 ms	129852 KB	Output is correct
8	Correct	114 ms	129852 KB	Output is correct
9	Correct	119 ms	129852 KB	Output is correct
10	Correct	115 ms	129852 KB	Output is correct
11	Correct	115 ms	129852 KB	Output is correct
12	Correct	112 ms	129852 KB	Output is correct
13	Correct	113 ms	129852 KB	Output is correct
14	Correct	115 ms	129852 KB	Output is correct
15	Correct	115 ms	129852 KB	Output is correct
16	Correct	112 ms	129852 KB	Output is correct
17	Correct	110 ms	129852 KB	Output is correct
18	Correct	131 ms	129852 KB	Output is correct
19	Correct	115 ms	129856 KB	Output is correct
20	Correct	117 ms	129856 KB	Output is correct
21	Correct	116 ms	129856 KB	Output is correct
22	Correct	123 ms	129856 KB	Output is correct
23	Correct	115 ms	129856 KB	Output is correct
24	Correct	113 ms	129856 KB	Output is correct
25	Correct	114 ms	129856 KB	Output is correct
26	Correct	113 ms	129856 KB	Output is correct
27	Correct	106 ms	129856 KB	Output is correct
28	Correct	118 ms	129856 KB	Output is correct
29	Correct	110 ms	129856 KB	Output is correct
30	Correct	113 ms	129856 KB	Output is correct
31	Correct	752 ms	142488 KB	Output is correct
32	Correct	172 ms	142488 KB	Output is correct
33	Correct	683 ms	142488 KB	Output is correct
34	Correct	754 ms	142488 KB	Output is correct
35	Correct	833 ms	142512 KB	Output is correct
36	Correct	766 ms	142512 KB	Output is correct
37	Correct	490 ms	142512 KB	Output is correct
38	Correct	502 ms	142512 KB	Output is correct
39	Correct	361 ms	142512 KB	Output is correct
40	Correct	498 ms	142512 KB	Output is correct
41	Correct	505 ms	142512 KB	Output is correct
42	Correct	439 ms	142512 KB	Output is correct
43	Correct	183 ms	142512 KB	Output is correct
44	Correct	526 ms	142512 KB	Output is correct
45	Correct	539 ms	142512 KB	Output is correct
46	Correct	413 ms	142512 KB	Output is correct
47	Correct	295 ms	142512 KB	Output is correct
48	Correct	293 ms	142512 KB	Output is correct
49	Correct	321 ms	142512 KB	Output is correct
50	Correct	356 ms	142512 KB	Output is correct
51	Correct	370 ms	142512 KB	Output is correct
52	Correct	3773 ms	204740 KB	Output is correct
53	Correct	4462 ms	204740 KB	Output is correct
54	Correct	3244 ms	249836 KB	Output is correct
55	Correct	3754 ms	249836 KB	Output is correct
56	Correct	3652 ms	249836 KB	Output is correct
57	Correct	4355 ms	249836 KB	Output is correct
58	Correct	2818 ms	249844 KB	Output is correct
59	Correct	2647 ms	249844 KB	Output is correct
60	Correct	2624 ms	249844 KB	Output is correct
61	Correct	3203 ms	249844 KB	Output is correct
62	Correct	1960 ms	249844 KB	Output is correct
63	Correct	1961 ms	249844 KB	Output is correct
64	Correct	4630 ms	249844 KB	Output is correct
65	Correct	429 ms	249844 KB	Output is correct
66	Execution timed out	5043 ms	249844 KB	Time limit exceeded
67	Halted	0 ms	0 KB	-

Submission #48866

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 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
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0