#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=200005;
vector< pair<int,int> > q[nmax],upd[nmax],pairs[nmax];
int a[nmax],b[nmax],h[nmax],l[nmax],r[nmax],ans[nmax];
int n,i,j,Q;
struct node
{
int nd,ll,rr;
}stv[100];
struct aint
{
int arb[4*nmax];
void update(int nod,int l,int r,int poz,int val)
{
if(l==r)
{
arb[nod]=val;
return;
}
int m=(l+r)/2;
if(poz<=m) update(2*nod,l,m,poz,val);
else update(2*nod+1,m+1,r,poz,val);
arb[nod]=min(arb[2*nod],arb[2*nod+1]);
}
int st,dr,mn;
void query(int nod,int l,int r)
{
if(st<=l&&r<=dr)
{
mn=min(mn,arb[nod]);
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m);
if(m<dr) query(2*nod+1,m+1,r);
}
int calc(int S,int D)
{
st=S;dr=D;mn=(1<<30);
query(1,1,n);
return mn;
}
int nr;
void gt(int nod,int l,int r)
{
if(st<=l&&r<=dr)
{
stv[++nr]={nod,l,r};
return;
}
int m=(l+r)/2;
if(st<=m) gt(2*nod,l,m);
if(m<dr) gt(2*nod+1,m+1,r);
}
int saved,where;
void cb(int nod,int l,int r,int cat)
{
if(l==r)
{
saved=arb[nod];
where=l;
return;
}
int m=(l+r)/2;
if(arb[2*nod+1]<=cat) cb(2*nod+1,m+1,r,cat);
else cb(2*nod,l,m,cat);
}
void roll(int source,int S,int D,int val)
{
int wanted=val-1;
bool ok=1;
while(ok&&S<=D)
{
if(calc(S,D)>wanted) ok=0;
else
{
st=S;dr=D;nr=0;
gt(1,1,n);
int it;
for(it=nr;it>=1&&arb[stv[it].nd]>wanted;it--);
cb(stv[it].nd,stv[it].ll,stv[it].rr,wanted);
wanted=val-2*(val-saved);D=where-1;
pairs[source].push_back({where,val-saved});
}
}
}
}mn,mx;
void solve()
{
for(i=1;i<=n;i++)
{
q[i].clear();
upd[i].clear();
pairs[i].clear();
}
for(i=1;i<=n;i++)
mn.update(1,1,n,i,(1<<30)),mx.update(1,1,n,i,(1<<30));
for(i=1;i<=n;i++)
{
if(i+a[i]<=n)upd[i+a[i]].push_back({i,h[i]});
if(i+b[i]+1<=n)upd[i+b[i]+1].push_back({i,(1<<30)});
}
for(i=1;i<=n;i++)
{
for(j=0;j<upd[i].size();j++)
{
mn.update(1,1,n,upd[i][j].first,upd[i][j].second);
}
mn.roll(i,max(i-b[i],1),i-a[i],h[i]);
}
for(i=1;i<=Q;i++)
{
q[r[i]].push_back({l[i],i});
}
for(i=1;i<=n;i++)
{
for(j=0;j<pairs[i].size();j++)
{
mx.update(1,1,n,pairs[i][j].first,-pairs[i][j].second);
}
for(j=0;j<q[i].size();j++)
{
int gt=-mx.calc(q[i][j].first,i);
if(gt>ans[q[i][j].second]) ans[q[i][j].second]=gt;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>h[i]>>a[i]>>b[i];
}
cin>>Q;
for(i=1;i<=Q;i++)
{
cin>>l[i]>>r[i];
ans[i]=-1;
}
solve();
reverse(h+1,h+n+1);
reverse(a+1,a+n+1);
reverse(b+1,b+n+1);
for(i=1;i<=Q;i++)
{
l[i]=n-l[i]+1;
r[i]=n-r[i]+1;
swap(l[i],r[i]);
}
solve();
for(i=1;i<=Q;i++)
cout<<ans[i]<<'\n';
return 0;
}
Compilation message
antennas.cpp: In function 'void solve()':
antennas.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<upd[i].size();j++)
~^~~~~~~~~~~~~~
antennas.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<pairs[i].size();j++)
~^~~~~~~~~~~~~~~~
antennas.cpp:125:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<q[i].size();j++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
553 ms |
32788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
