#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
inline char readchar(){
const int maxn=1000000;
static char buf[maxn],*p=buf,*q=buf;
if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
else return *p++;
}
inline int readint(){
int c=readchar(),x=0,neg=0;
while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
if(c=='-') neg=1,c=readchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
return neg?-x:x;
}
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=200005;
//i_am_noob
const int K=455;
int n,h[maxn],a[maxn],b[maxn],q,ans[maxn];
struct query{
int l,r,id;
}qry[maxn];
struct event{
int id,pos;
bool op;
};
vector<event> ev;
vector<int> vec[maxn/K+5];
int cur,cur1,vals[maxn],valb[maxn/K+5],cur2[maxn/K+5],minn[maxn/K+5],maxx[maxn/K+5];
multiset<int> st[maxn/K+5];
bool in[maxn];
inline void Insert(int id){
st[id/K].insert(h[id]);
}
inline void Erase(int id){
st[id/K].erase(st[id/K].find(h[id]));
}
inline void upd(int x){
rep2(i,x*K,min((x+1)*K,n)) if(in[i]) vals[i]=max(vals[i],max(h[i]-minn[x],maxx[x]-h[i]));
minn[x]=inf,maxx[x]=-inf;
}
inline void modifys(int x, int id){
bug(x,id);
if(in[x]){
bug(x,id);
vals[x]=max(vals[x],abs(h[x]-h[id]));
valb[x/K]=max(valb[x/K],vals[x]);
}
}
inline void modifyb(int x, int id){
if(sz(st[x])) valb[x]=max(valb[x],max(h[id]-(*st[x].begin()),(*st[x].rbegin())-h[id]));
minn[x]=min(minn[x],h[id]),maxx[x]=max(maxx[x],h[id]);
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
#ifdef i_am_noob
freopen("input1.txt","r",stdin);
freopen("output1.txt","w",stdout);
freopen("output2.txt","w",stderr);
#endif
cin >> n;
rep(n) cin >> h[i] >> a[i] >> b[i];
cin >> q;
rep(q) cin >> qry[i].l >> qry[i].r;
rep(q) qry[i].l--,qry[i].r--;
rep(q) qry[i].id=i;
sort(qry,qry+q,[&](query& i, query& j){return i.r<j.r;});
rep(n){
int x=i+a[i],y=i+b[i]+1;
if(x>=n) continue;
event tmp;
tmp.id=i,tmp.pos=x,tmp.op=1;
ev.pb(tmp);
vec[i/K].pb(x);
if(y<n){
tmp.id=i,tmp.pos=y,tmp.op=0;
ev.pb(tmp);
vec[i/K].pb(y);
}
}
sort(all(ev),[&](event& i, event& j){return i.pos<j.pos;});
rep(maxn/K) sort(all(vec[i])),vec[i].resize(unique(all(vec[i]))-vec[i].begin());
rep(maxn) vals[i]=-inf;
rep(maxn/K+5) valb[i]=-inf,minn[i]=inf,maxx[i]=-inf;
rep(n){
unordered_set<int> vis;
int tmp=cur1;
while(cur1<sz(ev)&&ev[cur1].pos==i){
if(ev[cur1].op) Insert(ev[cur1].id);
else Erase(ev[cur1].id);
vis.insert(ev[cur1].id/K);
cur1++;
}
for(auto j: vis) upd(j);
rep2(j,tmp,cur1){
if(ev[j].op) in[ev[j].id]=1;
else in[ev[j].id]=0;
}
int l=i-b[i],r=i-a[i];
bug(i,l,r);
rep1(j,n) if(in[j]) bug(j);
if(l<0) l=0;
for(; l%K&&l<=r; ++l) modifys(l,i);
for(; l+K<=r; l+=K) modifyb(l/K,i);
for(; l<=r; ++l) modifys(l,i);
while(cur<q&&qry[cur].r==i){
int res=-inf;
l=qry[cur].l,r=qry[cur].r;
for(; l%K&&l<=r; ++l){
res=max(res,vals[l]);
if(in[l]) res=max(res,max(h[l]-minn[l/K],maxx[l/K]-h[l]));
}
for(; l<=r; l+=K) res=max(res,valb[l/K]);
ans[qry[cur].id]=res;
cur++;
}
}
rep(q) cout << (ans[i]<0?-1:ans[i]) << "\n";
return 0;
}
Compilation message
antennas.cpp: In function 'void modifys(long long int, long long int)':
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
28 | #define bug(...) 826
| ^~~
antennas.cpp:81:5: note: in expansion of macro 'bug'
81 | bug(x,id);
| ^~~
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
28 | #define bug(...) 826
| ^~~
antennas.cpp:83:9: note: in expansion of macro 'bug'
83 | bug(x,id);
| ^~~
antennas.cpp: In function 'int main()':
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
28 | #define bug(...) 826
| ^~~
antennas.cpp:140:9: note: in expansion of macro 'bug'
140 | bug(i,l,r);
| ^~~
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
28 | #define bug(...) 826
| ^~~
antennas.cpp:141:29: note: in expansion of macro 'bug'
141 | rep1(j,n) if(in[j]) bug(j);
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
2 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
2 ms |
2028 KB |
Output is correct |
5 |
Correct |
2 ms |
2048 KB |
Output is correct |
6 |
Correct |
2 ms |
2028 KB |
Output is correct |
7 |
Correct |
3 ms |
2028 KB |
Output is correct |
8 |
Correct |
2 ms |
2028 KB |
Output is correct |
9 |
Correct |
2 ms |
2028 KB |
Output is correct |
10 |
Correct |
2 ms |
2028 KB |
Output is correct |
11 |
Correct |
2 ms |
2028 KB |
Output is correct |
12 |
Correct |
2 ms |
2028 KB |
Output is correct |
13 |
Correct |
2 ms |
2028 KB |
Output is correct |
14 |
Correct |
2 ms |
2028 KB |
Output is correct |
15 |
Correct |
2 ms |
2028 KB |
Output is correct |
16 |
Correct |
2 ms |
2028 KB |
Output is correct |
17 |
Correct |
2 ms |
2028 KB |
Output is correct |
18 |
Correct |
2 ms |
2028 KB |
Output is correct |
19 |
Correct |
2 ms |
2028 KB |
Output is correct |
20 |
Correct |
3 ms |
2028 KB |
Output is correct |
21 |
Correct |
2 ms |
2028 KB |
Output is correct |
22 |
Correct |
2 ms |
2028 KB |
Output is correct |
23 |
Correct |
2 ms |
2028 KB |
Output is correct |
24 |
Correct |
2 ms |
2028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
2 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
2 ms |
2028 KB |
Output is correct |
5 |
Correct |
2 ms |
2048 KB |
Output is correct |
6 |
Correct |
2 ms |
2028 KB |
Output is correct |
7 |
Correct |
3 ms |
2028 KB |
Output is correct |
8 |
Correct |
2 ms |
2028 KB |
Output is correct |
9 |
Correct |
2 ms |
2028 KB |
Output is correct |
10 |
Correct |
2 ms |
2028 KB |
Output is correct |
11 |
Correct |
2 ms |
2028 KB |
Output is correct |
12 |
Correct |
2 ms |
2028 KB |
Output is correct |
13 |
Correct |
2 ms |
2028 KB |
Output is correct |
14 |
Correct |
2 ms |
2028 KB |
Output is correct |
15 |
Correct |
2 ms |
2028 KB |
Output is correct |
16 |
Correct |
2 ms |
2028 KB |
Output is correct |
17 |
Correct |
2 ms |
2028 KB |
Output is correct |
18 |
Correct |
2 ms |
2028 KB |
Output is correct |
19 |
Correct |
2 ms |
2028 KB |
Output is correct |
20 |
Correct |
3 ms |
2028 KB |
Output is correct |
21 |
Correct |
2 ms |
2028 KB |
Output is correct |
22 |
Correct |
2 ms |
2028 KB |
Output is correct |
23 |
Correct |
2 ms |
2028 KB |
Output is correct |
24 |
Correct |
2 ms |
2028 KB |
Output is correct |
25 |
Correct |
105 ms |
9068 KB |
Output is correct |
26 |
Correct |
18 ms |
2924 KB |
Output is correct |
27 |
Correct |
156 ms |
11900 KB |
Output is correct |
28 |
Correct |
183 ms |
11988 KB |
Output is correct |
29 |
Correct |
104 ms |
9068 KB |
Output is correct |
30 |
Correct |
115 ms |
8812 KB |
Output is correct |
31 |
Correct |
101 ms |
11244 KB |
Output is correct |
32 |
Correct |
161 ms |
12028 KB |
Output is correct |
33 |
Correct |
142 ms |
11372 KB |
Output is correct |
34 |
Correct |
82 ms |
6892 KB |
Output is correct |
35 |
Correct |
154 ms |
11884 KB |
Output is correct |
36 |
Correct |
162 ms |
12012 KB |
Output is correct |
37 |
Correct |
74 ms |
7276 KB |
Output is correct |
38 |
Correct |
135 ms |
11116 KB |
Output is correct |
39 |
Correct |
22 ms |
3436 KB |
Output is correct |
40 |
Correct |
136 ms |
11116 KB |
Output is correct |
41 |
Correct |
95 ms |
8812 KB |
Output is correct |
42 |
Correct |
155 ms |
10988 KB |
Output is correct |
43 |
Correct |
54 ms |
5100 KB |
Output is correct |
44 |
Correct |
129 ms |
11116 KB |
Output is correct |
45 |
Correct |
23 ms |
3692 KB |
Output is correct |
46 |
Correct |
128 ms |
11072 KB |
Output is correct |
47 |
Correct |
36 ms |
4460 KB |
Output is correct |
48 |
Correct |
129 ms |
11124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
612 ms |
17284 KB |
Output is correct |
2 |
Correct |
716 ms |
19144 KB |
Output is correct |
3 |
Correct |
453 ms |
13840 KB |
Output is correct |
4 |
Correct |
703 ms |
19204 KB |
Output is correct |
5 |
Correct |
278 ms |
9744 KB |
Output is correct |
6 |
Correct |
737 ms |
19076 KB |
Output is correct |
7 |
Correct |
609 ms |
17040 KB |
Output is correct |
8 |
Correct |
732 ms |
19068 KB |
Output is correct |
9 |
Correct |
82 ms |
4760 KB |
Output is correct |
10 |
Correct |
722 ms |
18940 KB |
Output is correct |
11 |
Correct |
444 ms |
12756 KB |
Output is correct |
12 |
Correct |
722 ms |
19144 KB |
Output is correct |
13 |
Correct |
262 ms |
20604 KB |
Output is correct |
14 |
Correct |
212 ms |
18684 KB |
Output is correct |
15 |
Correct |
181 ms |
18740 KB |
Output is correct |
16 |
Correct |
255 ms |
19196 KB |
Output is correct |
17 |
Correct |
238 ms |
21628 KB |
Output is correct |
18 |
Correct |
243 ms |
19580 KB |
Output is correct |
19 |
Correct |
254 ms |
20476 KB |
Output is correct |
20 |
Correct |
223 ms |
19964 KB |
Output is correct |
21 |
Correct |
198 ms |
19196 KB |
Output is correct |
22 |
Correct |
223 ms |
19068 KB |
Output is correct |
23 |
Correct |
236 ms |
19144 KB |
Output is correct |
24 |
Correct |
202 ms |
19580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2028 KB |
Output is correct |
2 |
Correct |
2 ms |
2028 KB |
Output is correct |
3 |
Correct |
2 ms |
2028 KB |
Output is correct |
4 |
Correct |
2 ms |
2028 KB |
Output is correct |
5 |
Correct |
2 ms |
2048 KB |
Output is correct |
6 |
Correct |
2 ms |
2028 KB |
Output is correct |
7 |
Correct |
3 ms |
2028 KB |
Output is correct |
8 |
Correct |
2 ms |
2028 KB |
Output is correct |
9 |
Correct |
2 ms |
2028 KB |
Output is correct |
10 |
Correct |
2 ms |
2028 KB |
Output is correct |
11 |
Correct |
2 ms |
2028 KB |
Output is correct |
12 |
Correct |
2 ms |
2028 KB |
Output is correct |
13 |
Correct |
2 ms |
2028 KB |
Output is correct |
14 |
Correct |
2 ms |
2028 KB |
Output is correct |
15 |
Correct |
2 ms |
2028 KB |
Output is correct |
16 |
Correct |
2 ms |
2028 KB |
Output is correct |
17 |
Correct |
2 ms |
2028 KB |
Output is correct |
18 |
Correct |
2 ms |
2028 KB |
Output is correct |
19 |
Correct |
2 ms |
2028 KB |
Output is correct |
20 |
Correct |
3 ms |
2028 KB |
Output is correct |
21 |
Correct |
2 ms |
2028 KB |
Output is correct |
22 |
Correct |
2 ms |
2028 KB |
Output is correct |
23 |
Correct |
2 ms |
2028 KB |
Output is correct |
24 |
Correct |
2 ms |
2028 KB |
Output is correct |
25 |
Correct |
105 ms |
9068 KB |
Output is correct |
26 |
Correct |
18 ms |
2924 KB |
Output is correct |
27 |
Correct |
156 ms |
11900 KB |
Output is correct |
28 |
Correct |
183 ms |
11988 KB |
Output is correct |
29 |
Correct |
104 ms |
9068 KB |
Output is correct |
30 |
Correct |
115 ms |
8812 KB |
Output is correct |
31 |
Correct |
101 ms |
11244 KB |
Output is correct |
32 |
Correct |
161 ms |
12028 KB |
Output is correct |
33 |
Correct |
142 ms |
11372 KB |
Output is correct |
34 |
Correct |
82 ms |
6892 KB |
Output is correct |
35 |
Correct |
154 ms |
11884 KB |
Output is correct |
36 |
Correct |
162 ms |
12012 KB |
Output is correct |
37 |
Correct |
74 ms |
7276 KB |
Output is correct |
38 |
Correct |
135 ms |
11116 KB |
Output is correct |
39 |
Correct |
22 ms |
3436 KB |
Output is correct |
40 |
Correct |
136 ms |
11116 KB |
Output is correct |
41 |
Correct |
95 ms |
8812 KB |
Output is correct |
42 |
Correct |
155 ms |
10988 KB |
Output is correct |
43 |
Correct |
54 ms |
5100 KB |
Output is correct |
44 |
Correct |
129 ms |
11116 KB |
Output is correct |
45 |
Correct |
23 ms |
3692 KB |
Output is correct |
46 |
Correct |
128 ms |
11072 KB |
Output is correct |
47 |
Correct |
36 ms |
4460 KB |
Output is correct |
48 |
Correct |
129 ms |
11124 KB |
Output is correct |
49 |
Correct |
612 ms |
17284 KB |
Output is correct |
50 |
Correct |
716 ms |
19144 KB |
Output is correct |
51 |
Correct |
453 ms |
13840 KB |
Output is correct |
52 |
Correct |
703 ms |
19204 KB |
Output is correct |
53 |
Correct |
278 ms |
9744 KB |
Output is correct |
54 |
Correct |
737 ms |
19076 KB |
Output is correct |
55 |
Correct |
609 ms |
17040 KB |
Output is correct |
56 |
Correct |
732 ms |
19068 KB |
Output is correct |
57 |
Correct |
82 ms |
4760 KB |
Output is correct |
58 |
Correct |
722 ms |
18940 KB |
Output is correct |
59 |
Correct |
444 ms |
12756 KB |
Output is correct |
60 |
Correct |
722 ms |
19144 KB |
Output is correct |
61 |
Correct |
262 ms |
20604 KB |
Output is correct |
62 |
Correct |
212 ms |
18684 KB |
Output is correct |
63 |
Correct |
181 ms |
18740 KB |
Output is correct |
64 |
Correct |
255 ms |
19196 KB |
Output is correct |
65 |
Correct |
238 ms |
21628 KB |
Output is correct |
66 |
Correct |
243 ms |
19580 KB |
Output is correct |
67 |
Correct |
254 ms |
20476 KB |
Output is correct |
68 |
Correct |
223 ms |
19964 KB |
Output is correct |
69 |
Correct |
198 ms |
19196 KB |
Output is correct |
70 |
Correct |
223 ms |
19068 KB |
Output is correct |
71 |
Correct |
236 ms |
19144 KB |
Output is correct |
72 |
Correct |
202 ms |
19580 KB |
Output is correct |
73 |
Correct |
837 ms |
25320 KB |
Output is correct |
74 |
Correct |
733 ms |
19716 KB |
Output is correct |
75 |
Correct |
754 ms |
24720 KB |
Output is correct |
76 |
Correct |
1031 ms |
30084 KB |
Output is correct |
77 |
Correct |
473 ms |
17460 KB |
Output is correct |
78 |
Correct |
1004 ms |
26244 KB |
Output is correct |
79 |
Correct |
881 ms |
27664 KB |
Output is correct |
80 |
Correct |
1010 ms |
29816 KB |
Output is correct |
81 |
Correct |
307 ms |
14744 KB |
Output is correct |
82 |
Correct |
867 ms |
24188 KB |
Output is correct |
83 |
Correct |
690 ms |
23304 KB |
Output is correct |
84 |
Correct |
1002 ms |
30056 KB |
Output is correct |
85 |
Correct |
406 ms |
26168 KB |
Output is correct |
86 |
Correct |
436 ms |
28576 KB |
Output is correct |
87 |
Correct |
207 ms |
20220 KB |
Output is correct |
88 |
Correct |
444 ms |
28796 KB |
Output is correct |
89 |
Correct |
417 ms |
28576 KB |
Output is correct |
90 |
Correct |
455 ms |
29180 KB |
Output is correct |
91 |
Correct |
328 ms |
23804 KB |
Output is correct |
92 |
Correct |
437 ms |
29436 KB |
Output is correct |
93 |
Correct |
237 ms |
20860 KB |
Output is correct |
94 |
Correct |
453 ms |
28796 KB |
Output is correct |
95 |
Correct |
295 ms |
21500 KB |
Output is correct |
96 |
Correct |
403 ms |
29564 KB |
Output is correct |