oj.uz

Submission #251870

# Submission time Handle Problem Language Result Execution time Memory
251870 2020-07-22T13:16:30 Z oolimry New Home (APIO18_new_home) C++14
100 / 100
 1924 ms 78736 KB 
#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). It begins from start, and travells rightward. 

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 each type of store, find the lines which exist
	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}); ///this is in case some type doesn't exist at all, open(ii(2*INF,)) will be the last time a store existed
	}
	
	
	segmenttree tree; tree.init(); ///segment tree built over time
	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){ ///add all lines with start <= q.X
			line L = lines[lineptr];
			tree.update(L.open, L.close, L.xintercept);
			lineptr++;
		}
		
		q.ans = max(q.ans, tree.query(q.T) - q.X);
	}
}

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()); ///discretize time
	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(); ///discretize time
		}
		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; ///discretize time
		queries[i].id = i;
		queries[i].ans = 0;
	}
	sort(all(queries), [&](query a, query b){ return a.X < b.X; });
	
	solve(); ///solve for gradient = -1 slopes
	
	///reverse everything
	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(); ///solve for gradient = 1 slopes
	
	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
///It's hard to explain... oops

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 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 6 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 6 ms 7424 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 8 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 8 ms 7424 KB Output is correct
17 Correct 8 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 5 ms 7424 KB Output is correct
20 Correct 8 ms 7424 KB Output is correct
21 Correct 5 ms 7424 KB Output is correct
22 Correct 6 ms 7424 KB Output is correct
23 Correct 6 ms 7424 KB Output is correct
24 Correct 6 ms 7424 KB Output is correct
25 Correct 6 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 7 ms 7424 KB Output is correct
29 Correct 6 ms 7484 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 4 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 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 6 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 6 ms 7424 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 8 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 8 ms 7424 KB Output is correct
17 Correct 8 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 5 ms 7424 KB Output is correct
20 Correct 8 ms 7424 KB Output is correct
21 Correct 5 ms 7424 KB Output is correct
22 Correct 6 ms 7424 KB Output is correct
23 Correct 6 ms 7424 KB Output is correct
24 Correct 6 ms 7424 KB Output is correct
25 Correct 6 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 7 ms 7424 KB Output is correct
29 Correct 6 ms 7484 KB Output is correct
30 Correct 5 ms 7424 KB Output is correct
31 Correct 257 ms 21208 KB Output is correct
32 Correct 159 ms 18436 KB Output is correct
33 Correct 261 ms 20812 KB Output is correct
34 Correct 235 ms 21252 KB Output is correct
35 Correct 251 ms 20332 KB Output is correct
36 Correct 271 ms 20564 KB Output is correct
37 Correct 223 ms 20892 KB Output is correct
38 Correct 231 ms 20036 KB Output is correct
39 Correct 187 ms 19968 KB Output is correct
40 Correct 200 ms 20004 KB Output is correct
41 Correct 173 ms 20080 KB Output is correct
42 Correct 174 ms 20828 KB Output is correct
43 Correct 103 ms 20452 KB Output is correct
44 Correct 176 ms 20580 KB Output is correct
45 Correct 168 ms 20356 KB Output is correct
46 Correct 169 ms 20724 KB Output is correct
47 Correct 134 ms 19996 KB Output is correct
48 Correct 132 ms 19560 KB Output is correct
49 Correct 156 ms 20524 KB Output is correct
50 Correct 167 ms 20928 KB Output is correct
51 Correct 144 ms 20420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 58616 KB Output is correct
2 Correct 992 ms 55340 KB Output is correct
3 Correct 827 ms 74752 KB Output is correct
4 Correct 709 ms 58632 KB Output is correct
5 Correct 1412 ms 65632 KB Output is correct
6 Correct 1008 ms 55828 KB Output is correct
7 Correct 663 ms 74152 KB Output is correct
8 Correct 642 ms 56972 KB Output is correct
9 Correct 660 ms 56140 KB Output is correct
10 Correct 808 ms 54504 KB Output is correct
11 Correct 761 ms 53792 KB Output is correct
12 Correct 755 ms 55260 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 56264 KB Output is correct
2 Correct 758 ms 55212 KB Output is correct
3 Correct 1293 ms 54700 KB Output is correct
4 Correct 1079 ms 74140 KB Output is correct
5 Correct 1006 ms 58160 KB Output is correct
6 Correct 997 ms 58320 KB Output is correct
7 Correct 1924 ms 65340 KB Output is correct
8 Correct 1357 ms 55432 KB Output is correct
9 Correct 911 ms 73640 KB Output is correct
10 Correct 909 ms 57232 KB Output is correct
11 Correct 964 ms 55484 KB Output is correct
12 Correct 1123 ms 53416 KB Output is correct
13 Correct 839 ms 53348 KB Output is correct
14 Correct 865 ms 53908 KB Output is correct
15 Correct 925 ms 52868 KB Output is correct
16 Correct 964 ms 56544 KB Output is correct
17 Correct 1002 ms 53700 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 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 6 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 6 ms 7424 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 8 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 8 ms 7424 KB Output is correct
17 Correct 8 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 5 ms 7424 KB Output is correct
20 Correct 8 ms 7424 KB Output is correct
21 Correct 5 ms 7424 KB Output is correct
22 Correct 6 ms 7424 KB Output is correct
23 Correct 6 ms 7424 KB Output is correct
24 Correct 6 ms 7424 KB Output is correct
25 Correct 6 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 7 ms 7424 KB Output is correct
29 Correct 6 ms 7484 KB Output is correct
30 Correct 5 ms 7424 KB Output is correct
31 Correct 257 ms 21208 KB Output is correct
32 Correct 159 ms 18436 KB Output is correct
33 Correct 261 ms 20812 KB Output is correct
34 Correct 235 ms 21252 KB Output is correct
35 Correct 251 ms 20332 KB Output is correct
36 Correct 271 ms 20564 KB Output is correct
37 Correct 223 ms 20892 KB Output is correct
38 Correct 231 ms 20036 KB Output is correct
39 Correct 187 ms 19968 KB Output is correct
40 Correct 200 ms 20004 KB Output is correct
41 Correct 173 ms 20080 KB Output is correct
42 Correct 174 ms 20828 KB Output is correct
43 Correct 103 ms 20452 KB Output is correct
44 Correct 176 ms 20580 KB Output is correct
45 Correct 168 ms 20356 KB Output is correct
46 Correct 169 ms 20724 KB Output is correct
47 Correct 134 ms 19996 KB Output is correct
48 Correct 132 ms 19560 KB Output is correct
49 Correct 156 ms 20524 KB Output is correct
50 Correct 167 ms 20928 KB Output is correct
51 Correct 144 ms 20420 KB Output is correct
52 Correct 221 ms 21660 KB Output is correct
53 Correct 231 ms 21656 KB Output is correct
54 Correct 225 ms 21156 KB Output is correct
55 Correct 204 ms 21020 KB Output is correct
56 Correct 190 ms 21136 KB Output is correct
57 Correct 194 ms 20452 KB Output is correct
58 Correct 198 ms 21176 KB Output is correct
59 Correct 203 ms 21300 KB Output is correct
60 Correct 190 ms 20996 KB Output is correct
61 Correct 110 ms 21052 KB Output is correct
62 Correct 211 ms 21560 KB Output is correct
63 Correct 206 ms 21256 KB Output is correct
64 Correct 204 ms 20900 KB Output is correct
65 Correct 200 ms 20852 KB Output is correct
66 Correct 184 ms 20848 KB Output is correct
67 Correct 108 ms 18948 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 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 6 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 6 ms 7424 KB Output is correct
11 Correct 7 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 8 ms 7424 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 8 ms 7424 KB Output is correct
17 Correct 8 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 5 ms 7424 KB Output is correct
20 Correct 8 ms 7424 KB Output is correct
21 Correct 5 ms 7424 KB Output is correct
22 Correct 6 ms 7424 KB Output is correct
23 Correct 6 ms 7424 KB Output is correct
24 Correct 6 ms 7424 KB Output is correct
25 Correct 6 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 7 ms 7424 KB Output is correct
29 Correct 6 ms 7484 KB Output is correct
30 Correct 5 ms 7424 KB Output is correct
31 Correct 257 ms 21208 KB Output is correct
32 Correct 159 ms 18436 KB Output is correct
33 Correct 261 ms 20812 KB Output is correct
34 Correct 235 ms 21252 KB Output is correct
35 Correct 251 ms 20332 KB Output is correct
36 Correct 271 ms 20564 KB Output is correct
37 Correct 223 ms 20892 KB Output is correct
38 Correct 231 ms 20036 KB Output is correct
39 Correct 187 ms 19968 KB Output is correct
40 Correct 200 ms 20004 KB Output is correct
41 Correct 173 ms 20080 KB Output is correct
42 Correct 174 ms 20828 KB Output is correct
43 Correct 103 ms 20452 KB Output is correct
44 Correct 176 ms 20580 KB Output is correct
45 Correct 168 ms 20356 KB Output is correct
46 Correct 169 ms 20724 KB Output is correct
47 Correct 134 ms 19996 KB Output is correct
48 Correct 132 ms 19560 KB Output is correct
49 Correct 156 ms 20524 KB Output is correct
50 Correct 167 ms 20928 KB Output is correct
51 Correct 144 ms 20420 KB Output is correct
52 Correct 716 ms 58616 KB Output is correct
53 Correct 992 ms 55340 KB Output is correct
54 Correct 827 ms 74752 KB Output is correct
55 Correct 709 ms 58632 KB Output is correct
56 Correct 1412 ms 65632 KB Output is correct
57 Correct 1008 ms 55828 KB Output is correct
58 Correct 663 ms 74152 KB Output is correct
59 Correct 642 ms 56972 KB Output is correct
60 Correct 660 ms 56140 KB Output is correct
61 Correct 808 ms 54504 KB Output is correct
62 Correct 761 ms 53792 KB Output is correct
63 Correct 755 ms 55260 KB Output is correct
64 Correct 1022 ms 56264 KB Output is correct
65 Correct 758 ms 55212 KB Output is correct
66 Correct 1293 ms 54700 KB Output is correct
67 Correct 1079 ms 74140 KB Output is correct
68 Correct 1006 ms 58160 KB Output is correct
69 Correct 997 ms 58320 KB Output is correct
70 Correct 1924 ms 65340 KB Output is correct
71 Correct 1357 ms 55432 KB Output is correct
72 Correct 911 ms 73640 KB Output is correct
73 Correct 909 ms 57232 KB Output is correct
74 Correct 964 ms 55484 KB Output is correct
75 Correct 1123 ms 53416 KB Output is correct
76 Correct 839 ms 53348 KB Output is correct
77 Correct 865 ms 53908 KB Output is correct
78 Correct 925 ms 52868 KB Output is correct
79 Correct 964 ms 56544 KB Output is correct
80 Correct 1002 ms 53700 KB Output is correct
81 Correct 221 ms 21660 KB Output is correct
82 Correct 231 ms 21656 KB Output is correct
83 Correct 225 ms 21156 KB Output is correct
84 Correct 204 ms 21020 KB Output is correct
85 Correct 190 ms 21136 KB Output is correct
86 Correct 194 ms 20452 KB Output is correct
87 Correct 198 ms 21176 KB Output is correct
88 Correct 203 ms 21300 KB Output is correct
89 Correct 190 ms 20996 KB Output is correct
90 Correct 110 ms 21052 KB Output is correct
91 Correct 211 ms 21560 KB Output is correct
92 Correct 206 ms 21256 KB Output is correct
93 Correct 204 ms 20900 KB Output is correct
94 Correct 200 ms 20852 KB Output is correct
95 Correct 184 ms 20848 KB Output is correct
96 Correct 108 ms 18948 KB Output is correct
97 Correct 1296 ms 78416 KB Output is correct
98 Correct 824 ms 58244 KB Output is correct
99 Correct 1467 ms 60744 KB Output is correct
100 Correct 1327 ms 78736 KB Output is correct
101 Correct 1222 ms 62704 KB Output is correct
102 Correct 1513 ms 61108 KB Output is correct
103 Correct 1234 ms 60324 KB Output is correct
104 Correct 1321 ms 57548 KB Output is correct
105 Correct 1070 ms 57140 KB Output is correct
106 Correct 1158 ms 57336 KB Output is correct
107 Correct 1022 ms 59936 KB Output is correct
108 Correct 1058 ms 77804 KB Output is correct
109 Correct 964 ms 59560 KB Output is correct
110 Correct 1060 ms 60300 KB Output is correct
111 Correct 1184 ms 77400 KB Output is correct
112 Correct 1067 ms 58832 KB Output is correct
113 Correct 562 ms 77352 KB Output is correct
114 Correct 1188 ms 77332 KB Output is correct
115 Correct 1138 ms 77908 KB Output is correct
116 Correct 1095 ms 60036 KB Output is correct
117 Correct 1077 ms 59676 KB Output is correct
118 Correct 997 ms 59256 KB Output is correct
119 Correct 515 ms 58832 KB Output is correct
120 Correct 737 ms 54964 KB Output is correct
121 Correct 710 ms 56544 KB Output is correct
122 Correct 689 ms 53796 KB Output is correct
123 Correct 752 ms 57100 KB Output is correct
124 Correct 864 ms 56760 KB Output is correct
125 Correct 730 ms 57976 KB Output is correct
126 Correct 915 ms 59556 KB Output is correct