#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
struct event { int x,l,r,t; };
bool comp(event a,event b) {
if (a.x == b.x) return a.t > b.t;
else return a.x > b.x;
}
int H[200000],A[200000],B[200000],L[200000],R[200000];
int ans[200000];
vector<event> events;
int tree[1 << 19],best[1 << 19],lazy[1 << 19];
int build(int s,int e,int i) {
if (s == e) {
tree[i] = best[i] = -1,lazy[i] = 1e9;
return 0;
}
int mid = (s+e) / 2;
build(s,mid,2*i+1),build(mid+1,e,2*i+2);
tree[i] = best[i] = -1,lazy[i] = 1e9;
return 0;
}
int prop(int s,int e,int i) {
best[i] = max(best[i],tree[i]-lazy[i]);
if (s != e) lazy[2*i+1] = min(lazy[2*i+1],lazy[i]),lazy[2*i+2] = min(lazy[2*i+2],lazy[i]);
lazy[i] = 1e9;
return 0;
}
int update(int s,int e,int ai,int i,int num) {
prop(s,e,i);
if ((s > ai) || (e < ai)) return 0;
else if (s == e) {
tree[i] = num;
return 0;
}
int mid = (s+e) / 2;
update(s,mid,ai,2*i+1,num),update(mid+1,e,ai,2*i+2,num);
tree[i] = max(tree[2*i+1],tree[2*i+2]);
return 0;
}
int update2(int s,int e,int as,int ae,int i,int num) {
prop(s,e,i);
if ((s > ae) || (e < as)) return 0;
else if ((s >= as) && (e <= ae)) {
lazy[i] = min(lazy[i],num);
prop(s,e,i);
return 0;
}
int mid = (s+e) / 2;
update2(s,mid,as,ae,2*i+1,num),update2(mid+1,e,as,ae,2*i+2,num);
best[i] = max(best[i],max(best[2*i+1],best[2*i+2]));
return 0;
}
int query(int s,int e,int qs,int qe,int i) {
prop(s,e,i);
if ((s > qe) || (e < qs)) return -1;
else if ((s >= qs) && (e <= qe)) return best[i];
int mid = (s+e) / 2;
return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
int main() {
int i;
int N,Q;
scanf("%d",&N);
for (i = 0; i < N; i++) scanf("%d %d %d",&H[i],&A[i],&B[i]);
scanf("%d",&Q);
for (i = 0; i < Q; i++) scanf("%d %d",&L[i],&R[i]),L[i]--,R[i]--;
int j,r;
fill(ans,ans+Q,-1);
for (r = 0; r < 2; r++) {
for (i = 0; i < N; i++) {
events.pb((event){i-A[i],i,i,1});
events.pb((event){i-B[i],i,i,-1});
events.pb((event){i,i+A[i],i+B[i],0});
}
for (i = 0; i < Q; i++) events.pb((event){L[i],i,R[i],-2});
sort(events.begin(),events.end(),comp);
build(0,N-1,0);
for (i = 0; i < events.size(); i++) {
if (events[i].t == 1) update(0,N-1,events[i].l,0,H[events[i].l]);
else if (events[i].t == -1) update(0,N-1,events[i].l,0,-1);
else if (events[i].t == 0) update2(0,N-1,events[i].l,events[i].r,0,H[events[i].x]);
else ans[events[i].l] = max(ans[events[i].l],query(0,N-1,0,events[i].r,0));
}
events.clear();
for (i = 0; i < Q; i++) L[i] = N-L[i]-1,R[i] = N-R[i]-1,swap(L[i],R[i]);
reverse(A,A+N),reverse(B,B+N),reverse(H,H+N);
}
for (i = 0; i < Q; i++) printf("%d\n",ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < events.size(); i++) {
~~^~~~~~~~~~~~~~~
antennas.cpp:127:9: warning: unused variable 'j' [-Wunused-variable]
int j,r;
^
antennas.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
antennas.cpp:123:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < N; i++) scanf("%d %d %d",&H[i],&A[i],&B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&Q);
~~~~~^~~~~~~~~
antennas.cpp:125:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < Q; i++) scanf("%d %d",&L[i],&R[i]),L[i]--,R[i]--;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
3 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
512 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
3 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
512 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
134 ms |
6376 KB |
Output is correct |
26 |
Correct |
20 ms |
1148 KB |
Output is correct |
27 |
Correct |
190 ms |
7900 KB |
Output is correct |
28 |
Correct |
196 ms |
7888 KB |
Output is correct |
29 |
Correct |
133 ms |
6384 KB |
Output is correct |
30 |
Correct |
131 ms |
6228 KB |
Output is correct |
31 |
Correct |
161 ms |
7488 KB |
Output is correct |
32 |
Correct |
194 ms |
7900 KB |
Output is correct |
33 |
Correct |
172 ms |
7516 KB |
Output is correct |
34 |
Correct |
92 ms |
4072 KB |
Output is correct |
35 |
Correct |
193 ms |
7964 KB |
Output is correct |
36 |
Correct |
200 ms |
7892 KB |
Output is correct |
37 |
Correct |
109 ms |
4196 KB |
Output is correct |
38 |
Correct |
195 ms |
7008 KB |
Output is correct |
39 |
Correct |
29 ms |
1912 KB |
Output is correct |
40 |
Correct |
190 ms |
6992 KB |
Output is correct |
41 |
Correct |
138 ms |
6376 KB |
Output is correct |
42 |
Correct |
194 ms |
6980 KB |
Output is correct |
43 |
Correct |
63 ms |
3316 KB |
Output is correct |
44 |
Correct |
196 ms |
7016 KB |
Output is correct |
45 |
Correct |
37 ms |
1988 KB |
Output is correct |
46 |
Correct |
199 ms |
7016 KB |
Output is correct |
47 |
Correct |
50 ms |
2256 KB |
Output is correct |
48 |
Correct |
194 ms |
7008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
754 ms |
19080 KB |
Output is correct |
2 |
Correct |
861 ms |
19296 KB |
Output is correct |
3 |
Correct |
625 ms |
15068 KB |
Output is correct |
4 |
Correct |
855 ms |
19292 KB |
Output is correct |
5 |
Correct |
339 ms |
9828 KB |
Output is correct |
6 |
Correct |
845 ms |
19296 KB |
Output is correct |
7 |
Correct |
735 ms |
16852 KB |
Output is correct |
8 |
Correct |
842 ms |
19292 KB |
Output is correct |
9 |
Correct |
97 ms |
3184 KB |
Output is correct |
10 |
Correct |
871 ms |
19296 KB |
Output is correct |
11 |
Correct |
462 ms |
10960 KB |
Output is correct |
12 |
Correct |
879 ms |
19292 KB |
Output is correct |
13 |
Correct |
585 ms |
19292 KB |
Output is correct |
14 |
Correct |
574 ms |
19292 KB |
Output is correct |
15 |
Correct |
569 ms |
19296 KB |
Output is correct |
16 |
Correct |
551 ms |
19292 KB |
Output is correct |
17 |
Correct |
587 ms |
19308 KB |
Output is correct |
18 |
Correct |
569 ms |
19292 KB |
Output is correct |
19 |
Correct |
574 ms |
19292 KB |
Output is correct |
20 |
Correct |
581 ms |
19292 KB |
Output is correct |
21 |
Correct |
561 ms |
19292 KB |
Output is correct |
22 |
Correct |
573 ms |
19292 KB |
Output is correct |
23 |
Correct |
564 ms |
19292 KB |
Output is correct |
24 |
Correct |
550 ms |
19292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
3 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
3 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
512 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
134 ms |
6376 KB |
Output is correct |
26 |
Correct |
20 ms |
1148 KB |
Output is correct |
27 |
Correct |
190 ms |
7900 KB |
Output is correct |
28 |
Correct |
196 ms |
7888 KB |
Output is correct |
29 |
Correct |
133 ms |
6384 KB |
Output is correct |
30 |
Correct |
131 ms |
6228 KB |
Output is correct |
31 |
Correct |
161 ms |
7488 KB |
Output is correct |
32 |
Correct |
194 ms |
7900 KB |
Output is correct |
33 |
Correct |
172 ms |
7516 KB |
Output is correct |
34 |
Correct |
92 ms |
4072 KB |
Output is correct |
35 |
Correct |
193 ms |
7964 KB |
Output is correct |
36 |
Correct |
200 ms |
7892 KB |
Output is correct |
37 |
Correct |
109 ms |
4196 KB |
Output is correct |
38 |
Correct |
195 ms |
7008 KB |
Output is correct |
39 |
Correct |
29 ms |
1912 KB |
Output is correct |
40 |
Correct |
190 ms |
6992 KB |
Output is correct |
41 |
Correct |
138 ms |
6376 KB |
Output is correct |
42 |
Correct |
194 ms |
6980 KB |
Output is correct |
43 |
Correct |
63 ms |
3316 KB |
Output is correct |
44 |
Correct |
196 ms |
7016 KB |
Output is correct |
45 |
Correct |
37 ms |
1988 KB |
Output is correct |
46 |
Correct |
199 ms |
7016 KB |
Output is correct |
47 |
Correct |
50 ms |
2256 KB |
Output is correct |
48 |
Correct |
194 ms |
7008 KB |
Output is correct |
49 |
Correct |
754 ms |
19080 KB |
Output is correct |
50 |
Correct |
861 ms |
19296 KB |
Output is correct |
51 |
Correct |
625 ms |
15068 KB |
Output is correct |
52 |
Correct |
855 ms |
19292 KB |
Output is correct |
53 |
Correct |
339 ms |
9828 KB |
Output is correct |
54 |
Correct |
845 ms |
19296 KB |
Output is correct |
55 |
Correct |
735 ms |
16852 KB |
Output is correct |
56 |
Correct |
842 ms |
19292 KB |
Output is correct |
57 |
Correct |
97 ms |
3184 KB |
Output is correct |
58 |
Correct |
871 ms |
19296 KB |
Output is correct |
59 |
Correct |
462 ms |
10960 KB |
Output is correct |
60 |
Correct |
879 ms |
19292 KB |
Output is correct |
61 |
Correct |
585 ms |
19292 KB |
Output is correct |
62 |
Correct |
574 ms |
19292 KB |
Output is correct |
63 |
Correct |
569 ms |
19296 KB |
Output is correct |
64 |
Correct |
551 ms |
19292 KB |
Output is correct |
65 |
Correct |
587 ms |
19308 KB |
Output is correct |
66 |
Correct |
569 ms |
19292 KB |
Output is correct |
67 |
Correct |
574 ms |
19292 KB |
Output is correct |
68 |
Correct |
581 ms |
19292 KB |
Output is correct |
69 |
Correct |
561 ms |
19292 KB |
Output is correct |
70 |
Correct |
573 ms |
19292 KB |
Output is correct |
71 |
Correct |
564 ms |
19292 KB |
Output is correct |
72 |
Correct |
550 ms |
19292 KB |
Output is correct |
73 |
Correct |
984 ms |
24452 KB |
Output is correct |
74 |
Correct |
848 ms |
24160 KB |
Output is correct |
75 |
Correct |
851 ms |
28000 KB |
Output is correct |
76 |
Correct |
1190 ms |
32980 KB |
Output is correct |
77 |
Correct |
547 ms |
18216 KB |
Output is correct |
78 |
Correct |
1086 ms |
29628 KB |
Output is correct |
79 |
Correct |
1087 ms |
30820 KB |
Output is correct |
80 |
Correct |
1306 ms |
33108 KB |
Output is correct |
81 |
Correct |
335 ms |
14308 KB |
Output is correct |
82 |
Correct |
1008 ms |
27752 KB |
Output is correct |
83 |
Correct |
811 ms |
25968 KB |
Output is correct |
84 |
Correct |
1209 ms |
32900 KB |
Output is correct |
85 |
Correct |
817 ms |
27964 KB |
Output is correct |
86 |
Correct |
934 ms |
31804 KB |
Output is correct |
87 |
Correct |
615 ms |
24416 KB |
Output is correct |
88 |
Correct |
898 ms |
31640 KB |
Output is correct |
89 |
Correct |
839 ms |
29268 KB |
Output is correct |
90 |
Correct |
915 ms |
31696 KB |
Output is correct |
91 |
Correct |
702 ms |
25664 KB |
Output is correct |
92 |
Correct |
911 ms |
31700 KB |
Output is correct |
93 |
Correct |
631 ms |
24540 KB |
Output is correct |
94 |
Correct |
905 ms |
31684 KB |
Output is correct |
95 |
Correct |
652 ms |
25148 KB |
Output is correct |
96 |
Correct |
882 ms |
31764 KB |
Output is correct |