Submission #251868

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251868	2020-07-22T13:08:59 Z	oolimry	New Home (APIO18_new_home)	C++14	100 / 100	1882 ms	89428 KB

new_home

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define X first
#define T second
using namespace std;
typedef pair<int,int> ii;
typedef map<ii, int>::iterator iter;
const int MAXN = 300005;
const int INF = 2e8;

int n, K, Q, sz;
struct store { int X, id, T; };
struct query { int X, id, T, ans; };
struct line { int start, xintercept, open, close; }; ///line exists in time frame [open, close)

vector<store> stores[MAXN];
vector<query> queries;

struct segmenttree{
	vector<int> tree;
	void init(){
		tree.assign(2*sz,0);
	}
	
	void update(int l, int r, int v){
		for(l += sz, r += sz;l < r;l >>= 1, r >>= 1){
			if(l&1){
				tree[l] = max(tree[l], v);
				l++;
			}
			if(r&1){
				r--;
				tree[r] = max(tree[r], v);
			}
		}
	}
	
	int query(int i){
		int res = 0;
		for(i += sz;i > 0;i >>= 1) res = max(res, tree[i]);
		return res;
	}
};

map<ii, int> open; ///map<ii(location, index), time>
void solve(){
	vector<line> lines;
	
	for(int type = 1;type <= K;type++){
		open.clear();
		open[ii(-2*INF,0)] = 0;
		open[ii(2*INF,0)] = 0;
		
		for(store S : stores[type]){
			ii search = ii(S.X, S.id);
			iter cur = open.find(search);
			
			if(cur == open.end()){ ///S is going to be opened
				iter nxt = open.upper_bound(search);
				iter pre = prev(nxt);
				int nxtX = (nxt->first).X;
				int preX = (pre->first).X;
				
				lines.push_back({(nxtX + preX + 1)/2, nxtX, nxt->T, S.T});  ///line between nxt and pre broken when S is added 
				
				nxt->second = S.T; ///see footnote
				open[search] = S.T;
			}
			else{ ///S is going to be closed
				iter nxt = next(cur);
				iter pre = prev(cur);
				int nxtX = (nxt->first).X;
				int curX = (cur->first).X;
				int preX = (pre->first).X;
				
				lines.push_back({(nxtX + curX + 1)/2, nxtX, nxt->T, S.T}); ///line between nxt and cur broken when S is removed
				lines.push_back({(curX + preX + 1)/2, curX, cur->T, S.T}); ///line between cur and pre broken when S is removed
				
				nxt->second = S.T; ///see footnote
				open.erase(cur);
			}
		}
		lines.push_back({0, 2*INF, open[ii(2*INF,0)], sz});
	}
	
	//for(line L : lines){
	//	cout << L.start << " " << L.xintercept << " " << L.open << " " << L.close << "\n";
	//}
	//cout << "\n\n";		
	
	segmenttree tree; tree.init();
	sort(all(lines), [&](line a, line b){ return a.start < b.start; });
	
	int lineptr = 0;
	
	for(query &q : queries){
		while(lineptr < (int)lines.size() && lines[lineptr].start <= q.X){
			line L = lines[lineptr];
			tree.update(L.open, L.close, L.xintercept);
			//cout << L.open << " "  << L.close << " " << L.xintercept << "L\n";
			lineptr++;
		}
		
		q.ans = max(q.ans, tree.query(q.T) - q.X);
		//cout << q.X << " " << q.T << " " << q.ans << " " << tree.query(q.T) << "Q\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> K >> Q;
	
	vector<int> times;
	for(int i = 1;i <= n;i++){
		int X, type, A, B; cin >> X >> type >> A >> B;
		stores[type].push_back({X, i, A}); ///open
		stores[type].push_back({X, i, B+1}); ///close
		times.push_back(A);
		times.push_back(B+1);
	}
	
	sort(times.begin(), times.end());
	times.erase(unique(all(times)), times.end());
	sz = times.size();
	
	for(int type = 1;type <= K;type++){
		for(store &S : stores[type]){
			S.T = lower_bound(all(times), S.T) - times.begin();
			//cout << S.T << " " << S.X << "L\n";
		}
		sort(all(stores[type]), [&](store a, store b){
			return a.T < b.T; ///increasing X tiebreak by id
		});
	}
	
	queries.resize(Q);
	for(int i = 0;i < Q;i++){
		cin >> queries[i].X >> queries[i].T;
		queries[i].T = upper_bound(all(times), queries[i].T) - times.begin() - 1;
		//cout << queries[i].T << "T\n";
		queries[i].id = i;
		queries[i].ans = 0;
	}
	
	sort(all(queries), [&](query a, query b){ return a.X < b.X; });
	solve();
	
	for(query &q : queries) q.X = INF - q.X;
	reverse(all(queries));
	for(int type = 1;type <= K;type++){
		for(store &S : stores[type]) S.X = INF - S.X;
	}
	
	solve();
	
	sort(all(queries), [&](query a, query b){ return a.id < b.id; });
	for(query q : queries){
		if(q.ans >= INF) cout << "-1\n";
		else cout << q.ans << "\n";
	}
}

///footnote: it's kinda complicated... Basically by updating the right value, it's saying that any line which references the right range must start from the previous S->T

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7424 KB	Output is correct
2	Correct	4 ms	7424 KB	Output is correct
3	Correct	4 ms	7424 KB	Output is correct
4	Correct	4 ms	7424 KB	Output is correct
5	Correct	5 ms	7424 KB	Output is correct
6	Correct	6 ms	7424 KB	Output is correct
7	Correct	5 ms	7424 KB	Output is correct
8	Correct	5 ms	7424 KB	Output is correct
9	Correct	5 ms	7424 KB	Output is correct
10	Correct	5 ms	7424 KB	Output is correct
11	Correct	6 ms	7424 KB	Output is correct
12	Correct	5 ms	7424 KB	Output is correct
13	Correct	5 ms	7424 KB	Output is correct
14	Correct	6 ms	7424 KB	Output is correct
15	Correct	5 ms	7424 KB	Output is correct
16	Correct	5 ms	7424 KB	Output is correct
17	Correct	5 ms	7424 KB	Output is correct
18	Correct	5 ms	7424 KB	Output is correct
19	Correct	5 ms	7424 KB	Output is correct
20	Correct	5 ms	7424 KB	Output is correct
21	Correct	5 ms	7424 KB	Output is correct
22	Correct	5 ms	7424 KB	Output is correct
23	Correct	5 ms	7424 KB	Output is correct
24	Correct	5 ms	7424 KB	Output is correct
25	Correct	5 ms	7424 KB	Output is correct
26	Correct	5 ms	7424 KB	Output is correct
27	Correct	5 ms	7424 KB	Output is correct
28	Correct	5 ms	7424 KB	Output is correct
29	Correct	6 ms	7424 KB	Output is correct
30	Correct	5 ms	7424 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7424 KB	Output is correct
2	Correct	4 ms	7424 KB	Output is correct
3	Correct	4 ms	7424 KB	Output is correct
4	Correct	4 ms	7424 KB	Output is correct
5	Correct	5 ms	7424 KB	Output is correct
6	Correct	6 ms	7424 KB	Output is correct
7	Correct	5 ms	7424 KB	Output is correct
8	Correct	5 ms	7424 KB	Output is correct
9	Correct	5 ms	7424 KB	Output is correct
10	Correct	5 ms	7424 KB	Output is correct
11	Correct	6 ms	7424 KB	Output is correct
12	Correct	5 ms	7424 KB	Output is correct
13	Correct	5 ms	7424 KB	Output is correct
14	Correct	6 ms	7424 KB	Output is correct
15	Correct	5 ms	7424 KB	Output is correct
16	Correct	5 ms	7424 KB	Output is correct
17	Correct	5 ms	7424 KB	Output is correct
18	Correct	5 ms	7424 KB	Output is correct
19	Correct	5 ms	7424 KB	Output is correct
20	Correct	5 ms	7424 KB	Output is correct
21	Correct	5 ms	7424 KB	Output is correct
22	Correct	5 ms	7424 KB	Output is correct
23	Correct	5 ms	7424 KB	Output is correct
24	Correct	5 ms	7424 KB	Output is correct
25	Correct	5 ms	7424 KB	Output is correct
26	Correct	5 ms	7424 KB	Output is correct
27	Correct	5 ms	7424 KB	Output is correct
28	Correct	5 ms	7424 KB	Output is correct
29	Correct	6 ms	7424 KB	Output is correct
30	Correct	5 ms	7424 KB	Output is correct
31	Correct	237 ms	21344 KB	Output is correct
32	Correct	151 ms	18584 KB	Output is correct
33	Correct	249 ms	20824 KB	Output is correct
34	Correct	232 ms	21340 KB	Output is correct
35	Correct	248 ms	20548 KB	Output is correct
36	Correct	265 ms	20676 KB	Output is correct
37	Correct	220 ms	21080 KB	Output is correct
38	Correct	238 ms	20156 KB	Output is correct
39	Correct	199 ms	20084 KB	Output is correct
40	Correct	212 ms	20012 KB	Output is correct
41	Correct	185 ms	20216 KB	Output is correct
42	Correct	178 ms	20708 KB	Output is correct
43	Correct	108 ms	20536 KB	Output is correct
44	Correct	205 ms	20584 KB	Output is correct
45	Correct	173 ms	20352 KB	Output is correct
46	Correct	157 ms	20792 KB	Output is correct
47	Correct	139 ms	20120 KB	Output is correct
48	Correct	140 ms	19692 KB	Output is correct
49	Correct	155 ms	20528 KB	Output is correct
50	Correct	172 ms	20840 KB	Output is correct
51	Correct	149 ms	20420 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	731 ms	58220 KB	Output is correct
2	Correct	983 ms	54832 KB	Output is correct
3	Correct	888 ms	74280 KB	Output is correct
4	Correct	744 ms	58140 KB	Output is correct
5	Correct	1865 ms	65512 KB	Output is correct
6	Correct	1093 ms	56580 KB	Output is correct
7	Correct	739 ms	74788 KB	Output is correct
8	Correct	661 ms	57676 KB	Output is correct
9	Correct	715 ms	56780 KB	Output is correct
10	Correct	809 ms	55148 KB	Output is correct
11	Correct	783 ms	54424 KB	Output is correct
12	Correct	750 ms	55892 KB	Output is correct

Subtask #4
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1053 ms	56904 KB	Output is correct
2	Correct	796 ms	55848 KB	Output is correct
3	Correct	1339 ms	55424 KB	Output is correct
4	Correct	1125 ms	74792 KB	Output is correct
5	Correct	966 ms	58616 KB	Output is correct
6	Correct	977 ms	58760 KB	Output is correct
7	Correct	1882 ms	66116 KB	Output is correct
8	Correct	1373 ms	56772 KB	Output is correct
9	Correct	955 ms	74968 KB	Output is correct
10	Correct	894 ms	58256 KB	Output is correct
11	Correct	1022 ms	56408 KB	Output is correct
12	Correct	1137 ms	54952 KB	Output is correct
13	Correct	851 ms	54720 KB	Output is correct
14	Correct	902 ms	55504 KB	Output is correct
15	Correct	1126 ms	54296 KB	Output is correct
16	Correct	1000 ms	57788 KB	Output is correct
17	Correct	1077 ms	54956 KB	Output is correct

Subtask #5
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7424 KB	Output is correct
2	Correct	4 ms	7424 KB	Output is correct
3	Correct	4 ms	7424 KB	Output is correct
4	Correct	4 ms	7424 KB	Output is correct
5	Correct	5 ms	7424 KB	Output is correct
6	Correct	6 ms	7424 KB	Output is correct
7	Correct	5 ms	7424 KB	Output is correct
8	Correct	5 ms	7424 KB	Output is correct
9	Correct	5 ms	7424 KB	Output is correct
10	Correct	5 ms	7424 KB	Output is correct
11	Correct	6 ms	7424 KB	Output is correct
12	Correct	5 ms	7424 KB	Output is correct
13	Correct	5 ms	7424 KB	Output is correct
14	Correct	6 ms	7424 KB	Output is correct
15	Correct	5 ms	7424 KB	Output is correct
16	Correct	5 ms	7424 KB	Output is correct
17	Correct	5 ms	7424 KB	Output is correct
18	Correct	5 ms	7424 KB	Output is correct
19	Correct	5 ms	7424 KB	Output is correct
20	Correct	5 ms	7424 KB	Output is correct
21	Correct	5 ms	7424 KB	Output is correct
22	Correct	5 ms	7424 KB	Output is correct
23	Correct	5 ms	7424 KB	Output is correct
24	Correct	5 ms	7424 KB	Output is correct
25	Correct	5 ms	7424 KB	Output is correct
26	Correct	5 ms	7424 KB	Output is correct
27	Correct	5 ms	7424 KB	Output is correct
28	Correct	5 ms	7424 KB	Output is correct
29	Correct	6 ms	7424 KB	Output is correct
30	Correct	5 ms	7424 KB	Output is correct
31	Correct	237 ms	21344 KB	Output is correct
32	Correct	151 ms	18584 KB	Output is correct
33	Correct	249 ms	20824 KB	Output is correct
34	Correct	232 ms	21340 KB	Output is correct
35	Correct	248 ms	20548 KB	Output is correct
36	Correct	265 ms	20676 KB	Output is correct
37	Correct	220 ms	21080 KB	Output is correct
38	Correct	238 ms	20156 KB	Output is correct
39	Correct	199 ms	20084 KB	Output is correct
40	Correct	212 ms	20012 KB	Output is correct
41	Correct	185 ms	20216 KB	Output is correct
42	Correct	178 ms	20708 KB	Output is correct
43	Correct	108 ms	20536 KB	Output is correct
44	Correct	205 ms	20584 KB	Output is correct
45	Correct	173 ms	20352 KB	Output is correct
46	Correct	157 ms	20792 KB	Output is correct
47	Correct	139 ms	20120 KB	Output is correct
48	Correct	140 ms	19692 KB	Output is correct
49	Correct	155 ms	20528 KB	Output is correct
50	Correct	172 ms	20840 KB	Output is correct
51	Correct	149 ms	20420 KB	Output is correct
52	Correct	224 ms	21636 KB	Output is correct
53	Correct	220 ms	21800 KB	Output is correct
54	Correct	224 ms	21288 KB	Output is correct
55	Correct	191 ms	20900 KB	Output is correct
56	Correct	200 ms	21268 KB	Output is correct
57	Correct	203 ms	20492 KB	Output is correct
58	Correct	191 ms	21032 KB	Output is correct
59	Correct	212 ms	21128 KB	Output is correct
60	Correct	190 ms	20996 KB	Output is correct
61	Correct	107 ms	21048 KB	Output is correct
62	Correct	210 ms	21564 KB	Output is correct
63	Correct	209 ms	21264 KB	Output is correct
64	Correct	200 ms	21036 KB	Output is correct
65	Correct	200 ms	20852 KB	Output is correct
66	Correct	184 ms	20832 KB	Output is correct
67	Correct	105 ms	19076 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7424 KB	Output is correct
2	Correct	4 ms	7424 KB	Output is correct
3	Correct	4 ms	7424 KB	Output is correct
4	Correct	4 ms	7424 KB	Output is correct
5	Correct	5 ms	7424 KB	Output is correct
6	Correct	6 ms	7424 KB	Output is correct
7	Correct	5 ms	7424 KB	Output is correct
8	Correct	5 ms	7424 KB	Output is correct
9	Correct	5 ms	7424 KB	Output is correct
10	Correct	5 ms	7424 KB	Output is correct
11	Correct	6 ms	7424 KB	Output is correct
12	Correct	5 ms	7424 KB	Output is correct
13	Correct	5 ms	7424 KB	Output is correct
14	Correct	6 ms	7424 KB	Output is correct
15	Correct	5 ms	7424 KB	Output is correct
16	Correct	5 ms	7424 KB	Output is correct
17	Correct	5 ms	7424 KB	Output is correct
18	Correct	5 ms	7424 KB	Output is correct
19	Correct	5 ms	7424 KB	Output is correct
20	Correct	5 ms	7424 KB	Output is correct
21	Correct	5 ms	7424 KB	Output is correct
22	Correct	5 ms	7424 KB	Output is correct
23	Correct	5 ms	7424 KB	Output is correct
24	Correct	5 ms	7424 KB	Output is correct
25	Correct	5 ms	7424 KB	Output is correct
26	Correct	5 ms	7424 KB	Output is correct
27	Correct	5 ms	7424 KB	Output is correct
28	Correct	5 ms	7424 KB	Output is correct
29	Correct	6 ms	7424 KB	Output is correct
30	Correct	5 ms	7424 KB	Output is correct
31	Correct	237 ms	21344 KB	Output is correct
32	Correct	151 ms	18584 KB	Output is correct
33	Correct	249 ms	20824 KB	Output is correct
34	Correct	232 ms	21340 KB	Output is correct
35	Correct	248 ms	20548 KB	Output is correct
36	Correct	265 ms	20676 KB	Output is correct
37	Correct	220 ms	21080 KB	Output is correct
38	Correct	238 ms	20156 KB	Output is correct
39	Correct	199 ms	20084 KB	Output is correct
40	Correct	212 ms	20012 KB	Output is correct
41	Correct	185 ms	20216 KB	Output is correct
42	Correct	178 ms	20708 KB	Output is correct
43	Correct	108 ms	20536 KB	Output is correct
44	Correct	205 ms	20584 KB	Output is correct
45	Correct	173 ms	20352 KB	Output is correct
46	Correct	157 ms	20792 KB	Output is correct
47	Correct	139 ms	20120 KB	Output is correct
48	Correct	140 ms	19692 KB	Output is correct
49	Correct	155 ms	20528 KB	Output is correct
50	Correct	172 ms	20840 KB	Output is correct
51	Correct	149 ms	20420 KB	Output is correct
52	Correct	731 ms	58220 KB	Output is correct
53	Correct	983 ms	54832 KB	Output is correct
54	Correct	888 ms	74280 KB	Output is correct
55	Correct	744 ms	58140 KB	Output is correct
56	Correct	1865 ms	65512 KB	Output is correct
57	Correct	1093 ms	56580 KB	Output is correct
58	Correct	739 ms	74788 KB	Output is correct
59	Correct	661 ms	57676 KB	Output is correct
60	Correct	715 ms	56780 KB	Output is correct
61	Correct	809 ms	55148 KB	Output is correct
62	Correct	783 ms	54424 KB	Output is correct
63	Correct	750 ms	55892 KB	Output is correct
64	Correct	1053 ms	56904 KB	Output is correct
65	Correct	796 ms	55848 KB	Output is correct
66	Correct	1339 ms	55424 KB	Output is correct
67	Correct	1125 ms	74792 KB	Output is correct
68	Correct	966 ms	58616 KB	Output is correct
69	Correct	977 ms	58760 KB	Output is correct
70	Correct	1882 ms	66116 KB	Output is correct
71	Correct	1373 ms	56772 KB	Output is correct
72	Correct	955 ms	74968 KB	Output is correct
73	Correct	894 ms	58256 KB	Output is correct
74	Correct	1022 ms	56408 KB	Output is correct
75	Correct	1137 ms	54952 KB	Output is correct
76	Correct	851 ms	54720 KB	Output is correct
77	Correct	902 ms	55504 KB	Output is correct
78	Correct	1126 ms	54296 KB	Output is correct
79	Correct	1000 ms	57788 KB	Output is correct
80	Correct	1077 ms	54956 KB	Output is correct
81	Correct	224 ms	21636 KB	Output is correct
82	Correct	220 ms	21800 KB	Output is correct
83	Correct	224 ms	21288 KB	Output is correct
84	Correct	191 ms	20900 KB	Output is correct
85	Correct	200 ms	21268 KB	Output is correct
86	Correct	203 ms	20492 KB	Output is correct
87	Correct	191 ms	21032 KB	Output is correct
88	Correct	212 ms	21128 KB	Output is correct
89	Correct	190 ms	20996 KB	Output is correct
90	Correct	107 ms	21048 KB	Output is correct
91	Correct	210 ms	21564 KB	Output is correct
92	Correct	209 ms	21264 KB	Output is correct
93	Correct	200 ms	21036 KB	Output is correct
94	Correct	200 ms	20852 KB	Output is correct
95	Correct	184 ms	20832 KB	Output is correct
96	Correct	105 ms	19076 KB	Output is correct
97	Correct	1308 ms	88764 KB	Output is correct
98	Correct	883 ms	58124 KB	Output is correct
99	Correct	1481 ms	69576 KB	Output is correct
100	Correct	1298 ms	89000 KB	Output is correct
101	Correct	1181 ms	72484 KB	Output is correct
102	Correct	1549 ms	69892 KB	Output is correct
103	Correct	1276 ms	69304 KB	Output is correct
104	Correct	1367 ms	66620 KB	Output is correct
105	Correct	1134 ms	66360 KB	Output is correct
106	Correct	1158 ms	66536 KB	Output is correct
107	Correct	996 ms	70844 KB	Output is correct
108	Correct	1092 ms	88548 KB	Output is correct
109	Correct	975 ms	70376 KB	Output is correct
110	Correct	1044 ms	71328 KB	Output is correct
111	Correct	1089 ms	88788 KB	Output is correct
112	Correct	968 ms	70016 KB	Output is correct
113	Correct	554 ms	85680 KB	Output is correct
114	Correct	1260 ms	88752 KB	Output is correct
115	Correct	1185 ms	89428 KB	Output is correct
116	Correct	1175 ms	71436 KB	Output is correct
117	Correct	1084 ms	71360 KB	Output is correct
118	Correct	1064 ms	70652 KB	Output is correct
119	Correct	533 ms	61644 KB	Output is correct
120	Correct	629 ms	65208 KB	Output is correct
121	Correct	682 ms	67424 KB	Output is correct
122	Correct	684 ms	64764 KB	Output is correct
123	Correct	754 ms	68372 KB	Output is correct
124	Correct	848 ms	68920 KB	Output is correct
125	Correct	734 ms	69540 KB	Output is correct
126	Correct	938 ms	72036 KB	Output is correct

Submission #251868

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 20.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
20.0 / 20.0