#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
using vEvents = vector<pair<int, pair<int, int>>>;
struct LazySegTree {
vector<int> max_array;
vector<int> del;
LazySegTree () = default;
LazySegTree (int size) {
max_array.resize(size, 0);
del.resize(size, - 1e9);
}
void update (int l, int r, int mx) {
if (r < 0) return ;
if (l < 0) l = 0;
for (int i = l; i <= r; i ++)
max_array[i] = max(max_array[i], mx);
}
void set (int index, int mx, int delta) {
max_array[index] = mx;
del[index] = delta;
}
int query (int l, int r) {
int res = -1e9;
for (int i = l; i <= r; i ++)
res = max(res, max_array[i] + del[i]);
return res;
}
int get (int i) {
return max_array[i] + del[i];
}
};
struct QueryManager {
idata A, B, H;
vEvents events;
int iEv = 0;
LazySegTree s_prov;
LazySegTree s_fina;
int right = -1;
QueryManager (idata _A, idata _B, idata _H) {
A = _A; B = _B; H = _H;
s_prov = LazySegTree(A.size());
s_fina = LazySegTree(A.size());
for (int i = 0; i < A.size(); i ++) {
events.push_back({ i + A[i], { i, 0 } });
events.push_back({ i + B[i] + 1, { i, 1 } });
}
sort(events.begin(), events.end());
}
void increase () {
right ++;
while (iEv != events.size() && events[iEv].first == right) {
const auto event = events[iEv]; iEv ++;
int id = event.second.first;
int ty = event.second.second;
if (ty == 0) {
s_prov.set(id, H[id] - 1, - H[id]);
} else if (ty == 1) {
int loc = s_prov.get(id);
s_prov.set(id, 0, - 1e9);
s_fina.set(id, loc, 0);
}
}
s_prov.update(right - B[right], right - A[right], H[right]);
}
void update (int target) {
while (right < target) increase();
}
int query (int qleft, int qright) {
update(qright);
return max(s_prov.query(qleft, qright), s_fina.query(qleft, qright));
}
};
int main () {
int N;
cin >> N;
idata H(N), A(N), B(N);
for (int i = 0; i < N; i ++)
cin >> H[i] >> A[i] >> B[i];
QueryManager table_pos(A, B, H);
for (int i = 0; i < N; i ++)
H[i] *= -1;
QueryManager table_neg(A, B, H);
int Q; cin >> Q;
vector<pair<pair<int, int>, int>> queries;
idata answers(Q);
for (int q = 0; q < Q; q ++) {
int a, b;
cin >> a >> b;
a --; b --;
queries.push_back({ {b, a}, q });
}
sort(queries.begin(), queries.end());
for (const auto &query : queries) {
answers[query.second] = max(
table_pos.query( query.first.second, query.first.first ),
table_neg.query( query.first.second, query.first.first )
);
if (answers[query.second] < 0) answers[query.second] = -1;
}
for (int u : answers) cout << u << "\n";
}
Compilation message
antennas.cpp: In constructor 'QueryManager::QueryManager(idata, idata, idata)':
antennas.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < A.size(); i ++) {
| ~~^~~~~~~~~~
antennas.cpp: In member function 'void QueryManager::increase()':
antennas.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while (iEv != events.size() && events[iEv].first == right) {
| ~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
190 ms |
4788 KB |
Output is correct |
26 |
Correct |
37 ms |
1136 KB |
Output is correct |
27 |
Correct |
405 ms |
7348 KB |
Output is correct |
28 |
Correct |
476 ms |
7428 KB |
Output is correct |
29 |
Correct |
201 ms |
5300 KB |
Output is correct |
30 |
Correct |
317 ms |
5596 KB |
Output is correct |
31 |
Correct |
144 ms |
6448 KB |
Output is correct |
32 |
Correct |
472 ms |
7496 KB |
Output is correct |
33 |
Correct |
308 ms |
6892 KB |
Output is correct |
34 |
Correct |
230 ms |
3964 KB |
Output is correct |
35 |
Correct |
370 ms |
7308 KB |
Output is correct |
36 |
Correct |
473 ms |
7376 KB |
Output is correct |
37 |
Correct |
261 ms |
3952 KB |
Output is correct |
38 |
Correct |
471 ms |
6472 KB |
Output is correct |
39 |
Correct |
65 ms |
1476 KB |
Output is correct |
40 |
Correct |
467 ms |
6472 KB |
Output is correct |
41 |
Correct |
337 ms |
5612 KB |
Output is correct |
42 |
Correct |
469 ms |
6404 KB |
Output is correct |
43 |
Correct |
151 ms |
2508 KB |
Output is correct |
44 |
Correct |
458 ms |
6404 KB |
Output is correct |
45 |
Correct |
79 ms |
1936 KB |
Output is correct |
46 |
Correct |
464 ms |
6468 KB |
Output is correct |
47 |
Correct |
119 ms |
2176 KB |
Output is correct |
48 |
Correct |
463 ms |
6476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3020 ms |
27764 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
190 ms |
4788 KB |
Output is correct |
26 |
Correct |
37 ms |
1136 KB |
Output is correct |
27 |
Correct |
405 ms |
7348 KB |
Output is correct |
28 |
Correct |
476 ms |
7428 KB |
Output is correct |
29 |
Correct |
201 ms |
5300 KB |
Output is correct |
30 |
Correct |
317 ms |
5596 KB |
Output is correct |
31 |
Correct |
144 ms |
6448 KB |
Output is correct |
32 |
Correct |
472 ms |
7496 KB |
Output is correct |
33 |
Correct |
308 ms |
6892 KB |
Output is correct |
34 |
Correct |
230 ms |
3964 KB |
Output is correct |
35 |
Correct |
370 ms |
7308 KB |
Output is correct |
36 |
Correct |
473 ms |
7376 KB |
Output is correct |
37 |
Correct |
261 ms |
3952 KB |
Output is correct |
38 |
Correct |
471 ms |
6472 KB |
Output is correct |
39 |
Correct |
65 ms |
1476 KB |
Output is correct |
40 |
Correct |
467 ms |
6472 KB |
Output is correct |
41 |
Correct |
337 ms |
5612 KB |
Output is correct |
42 |
Correct |
469 ms |
6404 KB |
Output is correct |
43 |
Correct |
151 ms |
2508 KB |
Output is correct |
44 |
Correct |
458 ms |
6404 KB |
Output is correct |
45 |
Correct |
79 ms |
1936 KB |
Output is correct |
46 |
Correct |
464 ms |
6468 KB |
Output is correct |
47 |
Correct |
119 ms |
2176 KB |
Output is correct |
48 |
Correct |
463 ms |
6476 KB |
Output is correct |
49 |
Execution timed out |
3020 ms |
27764 KB |
Time limit exceeded |
50 |
Halted |
0 ms |
0 KB |
- |