//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=2005;
multiset<ll> segtree[mxn*4];
ll h[mxn],a[mxn],b[mxn];
int n,q;
ll val;
void update(int pos,int l=1,int r=n,int v=1){
if(l>r) return;
segtree[v].insert(h[pos]);
if(l==r) return;
int mid=(l+r)/2;
if(pos<=mid) update(pos,l,mid,v*2);
else update(pos,mid+1,r,v*2+1);
}
void erase(int pos,int l=1,int r=n,int v=1){
if(l>r) return;
segtree[v].erase(segtree[v].find(h[pos]));
if(l==r) return;
int mid=(l+r)/2;
if(pos<=mid) erase(pos,l,mid,v*2);
else erase(pos,mid+1,r,v*2+1);
}
ll mnquery(int tl,int tr,int l=1,int r=n,int v=1){
if(r<tl or tr<l){
return 2e9;
}
if(tl<=l and r<=tr){
return (segtree[v].empty()?(2e9):*segtree[v].begin());
}
int mid=(l+r)/2;
return min(mnquery(tl,min(mid,tr),l,mid,v*2),mnquery(max(tl,mid+1),tr,mid+1,r,v*2+1));
}
ll mxquery(int tl,int tr,int l=1,int r=n,int v=1){
if(r<tl or tr<l){
return -2e9;
}
if(tl<=l and r<=tr){
return (segtree[v].empty()?(-2e9):*segtree[v].rbegin());
}
int mid=(l+r)/2;
return max(mxquery(tl,min(mid,tr),l,mid,v*2),mxquery(max(tl,mid+1),tr,mid+1,r,v*2+1));
}
int main() {_
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i]>>a[i]>>b[i];
}
cin>>q;
vector<pair<ll,ll>> R[mxn];
for(int i=0;i<q;i++){
ll l,r;
cin>>l>>r;
R[r].push_back({i,l});
}
vector<ll> output(q);
for(ll i=1;i<=n;i++){
for(int j=0;j<mxn*4;j++){
segtree[j].clear();
}
vector<int> st[mxn],en[mxn];
for(int j=1;j<=i;j++){
if(j-b[j]+1>i or j-a[j]+1<1) continue;
//cout<<max(l,j-b[j])<<' '<<min(r,j-a[j])+1<<'\n';
st[max(1ll,j-b[j])].push_back(j);
en[min(i,j-a[j])+1].push_back(j);
}
vector<ll> rec(mxn);
for(int j=1;j<=i;j++){
ll ans=-1;
for(auto v:st[j]){
update(v);
}
for(auto v:en[j]){
erase(v);
}
rec[j]=-1;
ll L=j+a[j];
ll R=j+b[j];
if(L>i or R<1) continue;
L=max(L,1ll);
R=min(R,i);
val=h[j];
if(mnquery(L,R)!=2e9) ans=max(ans,abs(h[j]-mnquery(L,R)));
if(mxquery(L,R)!=-2e9) ans=max(ans,abs(h[j]-mxquery(L,R)));
rec[j]=ans;
}
for(int j=i-1;j>=1;j--){
rec[j]=max(rec[j],rec[j+1]);
}
for(auto v:R[i]){
output[v.f]=rec[v.s];
}
}
for(int i=0;i<q;i++){
cout<<output[i]<<'\n';
}
return 0;
}
//maybe its multiset not set
Compilation message
antennas.cpp: In function 'void setIO(std::string)':
antennas.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
856 KB |
Output is correct |
2 |
Correct |
28 ms |
1040 KB |
Output is correct |
3 |
Correct |
13 ms |
860 KB |
Output is correct |
4 |
Correct |
21 ms |
860 KB |
Output is correct |
5 |
Correct |
15 ms |
1024 KB |
Output is correct |
6 |
Correct |
22 ms |
860 KB |
Output is correct |
7 |
Correct |
17 ms |
860 KB |
Output is correct |
8 |
Correct |
23 ms |
1032 KB |
Output is correct |
9 |
Correct |
4 ms |
856 KB |
Output is correct |
10 |
Correct |
22 ms |
1036 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
21 ms |
1044 KB |
Output is correct |
13 |
Correct |
19 ms |
860 KB |
Output is correct |
14 |
Correct |
14 ms |
1116 KB |
Output is correct |
15 |
Correct |
13 ms |
860 KB |
Output is correct |
16 |
Correct |
13 ms |
1032 KB |
Output is correct |
17 |
Correct |
24 ms |
860 KB |
Output is correct |
18 |
Correct |
20 ms |
1044 KB |
Output is correct |
19 |
Correct |
15 ms |
856 KB |
Output is correct |
20 |
Correct |
15 ms |
1112 KB |
Output is correct |
21 |
Correct |
13 ms |
860 KB |
Output is correct |
22 |
Correct |
15 ms |
1044 KB |
Output is correct |
23 |
Correct |
13 ms |
864 KB |
Output is correct |
24 |
Correct |
13 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
856 KB |
Output is correct |
2 |
Correct |
28 ms |
1040 KB |
Output is correct |
3 |
Correct |
13 ms |
860 KB |
Output is correct |
4 |
Correct |
21 ms |
860 KB |
Output is correct |
5 |
Correct |
15 ms |
1024 KB |
Output is correct |
6 |
Correct |
22 ms |
860 KB |
Output is correct |
7 |
Correct |
17 ms |
860 KB |
Output is correct |
8 |
Correct |
23 ms |
1032 KB |
Output is correct |
9 |
Correct |
4 ms |
856 KB |
Output is correct |
10 |
Correct |
22 ms |
1036 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
21 ms |
1044 KB |
Output is correct |
13 |
Correct |
19 ms |
860 KB |
Output is correct |
14 |
Correct |
14 ms |
1116 KB |
Output is correct |
15 |
Correct |
13 ms |
860 KB |
Output is correct |
16 |
Correct |
13 ms |
1032 KB |
Output is correct |
17 |
Correct |
24 ms |
860 KB |
Output is correct |
18 |
Correct |
20 ms |
1044 KB |
Output is correct |
19 |
Correct |
15 ms |
856 KB |
Output is correct |
20 |
Correct |
15 ms |
1112 KB |
Output is correct |
21 |
Correct |
13 ms |
860 KB |
Output is correct |
22 |
Correct |
15 ms |
1044 KB |
Output is correct |
23 |
Correct |
13 ms |
864 KB |
Output is correct |
24 |
Correct |
13 ms |
860 KB |
Output is correct |
25 |
Correct |
256 ms |
7572 KB |
Output is correct |
26 |
Correct |
1211 ms |
1884 KB |
Output is correct |
27 |
Correct |
863 ms |
10800 KB |
Output is correct |
28 |
Correct |
1356 ms |
11080 KB |
Output is correct |
29 |
Correct |
311 ms |
7892 KB |
Output is correct |
30 |
Correct |
1333 ms |
7648 KB |
Output is correct |
31 |
Correct |
51 ms |
9628 KB |
Output is correct |
32 |
Correct |
1390 ms |
10872 KB |
Output is correct |
33 |
Correct |
472 ms |
10348 KB |
Output is correct |
34 |
Correct |
1321 ms |
5932 KB |
Output is correct |
35 |
Correct |
670 ms |
10660 KB |
Output is correct |
36 |
Correct |
1304 ms |
11092 KB |
Output is correct |
37 |
Correct |
762 ms |
6112 KB |
Output is correct |
38 |
Correct |
915 ms |
10056 KB |
Output is correct |
39 |
Correct |
1330 ms |
2696 KB |
Output is correct |
40 |
Correct |
920 ms |
10324 KB |
Output is correct |
41 |
Correct |
1143 ms |
7608 KB |
Output is correct |
42 |
Correct |
1530 ms |
10368 KB |
Output is correct |
43 |
Correct |
727 ms |
4500 KB |
Output is correct |
44 |
Correct |
1020 ms |
10132 KB |
Output is correct |
45 |
Correct |
767 ms |
2844 KB |
Output is correct |
46 |
Correct |
1080 ms |
10104 KB |
Output is correct |
47 |
Correct |
772 ms |
3412 KB |
Output is correct |
48 |
Correct |
928 ms |
10324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
11 ms |
1628 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
856 KB |
Output is correct |
2 |
Correct |
28 ms |
1040 KB |
Output is correct |
3 |
Correct |
13 ms |
860 KB |
Output is correct |
4 |
Correct |
21 ms |
860 KB |
Output is correct |
5 |
Correct |
15 ms |
1024 KB |
Output is correct |
6 |
Correct |
22 ms |
860 KB |
Output is correct |
7 |
Correct |
17 ms |
860 KB |
Output is correct |
8 |
Correct |
23 ms |
1032 KB |
Output is correct |
9 |
Correct |
4 ms |
856 KB |
Output is correct |
10 |
Correct |
22 ms |
1036 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
21 ms |
1044 KB |
Output is correct |
13 |
Correct |
19 ms |
860 KB |
Output is correct |
14 |
Correct |
14 ms |
1116 KB |
Output is correct |
15 |
Correct |
13 ms |
860 KB |
Output is correct |
16 |
Correct |
13 ms |
1032 KB |
Output is correct |
17 |
Correct |
24 ms |
860 KB |
Output is correct |
18 |
Correct |
20 ms |
1044 KB |
Output is correct |
19 |
Correct |
15 ms |
856 KB |
Output is correct |
20 |
Correct |
15 ms |
1112 KB |
Output is correct |
21 |
Correct |
13 ms |
860 KB |
Output is correct |
22 |
Correct |
15 ms |
1044 KB |
Output is correct |
23 |
Correct |
13 ms |
864 KB |
Output is correct |
24 |
Correct |
13 ms |
860 KB |
Output is correct |
25 |
Correct |
256 ms |
7572 KB |
Output is correct |
26 |
Correct |
1211 ms |
1884 KB |
Output is correct |
27 |
Correct |
863 ms |
10800 KB |
Output is correct |
28 |
Correct |
1356 ms |
11080 KB |
Output is correct |
29 |
Correct |
311 ms |
7892 KB |
Output is correct |
30 |
Correct |
1333 ms |
7648 KB |
Output is correct |
31 |
Correct |
51 ms |
9628 KB |
Output is correct |
32 |
Correct |
1390 ms |
10872 KB |
Output is correct |
33 |
Correct |
472 ms |
10348 KB |
Output is correct |
34 |
Correct |
1321 ms |
5932 KB |
Output is correct |
35 |
Correct |
670 ms |
10660 KB |
Output is correct |
36 |
Correct |
1304 ms |
11092 KB |
Output is correct |
37 |
Correct |
762 ms |
6112 KB |
Output is correct |
38 |
Correct |
915 ms |
10056 KB |
Output is correct |
39 |
Correct |
1330 ms |
2696 KB |
Output is correct |
40 |
Correct |
920 ms |
10324 KB |
Output is correct |
41 |
Correct |
1143 ms |
7608 KB |
Output is correct |
42 |
Correct |
1530 ms |
10368 KB |
Output is correct |
43 |
Correct |
727 ms |
4500 KB |
Output is correct |
44 |
Correct |
1020 ms |
10132 KB |
Output is correct |
45 |
Correct |
767 ms |
2844 KB |
Output is correct |
46 |
Correct |
1080 ms |
10104 KB |
Output is correct |
47 |
Correct |
772 ms |
3412 KB |
Output is correct |
48 |
Correct |
928 ms |
10324 KB |
Output is correct |
49 |
Runtime error |
11 ms |
1628 KB |
Execution killed with signal 11 |
50 |
Halted |
0 ms |
0 KB |
- |