#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n;
llo it[200001];
pair<llo,llo> aa[200001];
vector<pair<llo,llo>> pre[200001];
llo tree[800001];//max values
multiset<pair<pair<llo,llo>,llo>> tree2[800001];//valid segments
multiset<llo> tree3[800001];//current valid heights
multiset<llo> tree5[800001];//current valid heights
vector<pair<llo,llo>> lazy[800001];//lazy
vector<pair<pair<llo,llo>,llo>> tree4[800001];
llo pollo[800001];
llo ans[200001];
bool cmp(pair<pair<llo,llo>,llo> d,pair<pair<llo,llo>,llo> e){
return d.a.b<e.a.b;
}
void push(llo no,llo bet,llo val){
// cout<<no<<"::"<<bet<<"::"<<val<<endl;
while(pollo[no]>=0){
if(tree4[no][pollo[no]].a.b>=bet){
tree3[no].insert(tree4[no][pollo[no]].b);
tree5[no].insert(-tree4[no][pollo[no]].b);
tree2[no].insert({{-tree4[no][pollo[no]].a.a,tree4[no][pollo[no]].a.b},tree4[no][pollo[no]].b});
//tree2[no].insert(tree4[no][pollo[no]]);
pollo[no]--;
}
else{
break;
}
}
while(tree2[no].size()){
if(-(*tree2[no].begin()).a.a>bet){
auto k=tree3[no].find((*tree2[no].begin()).b);
tree3[no].erase(k);
auto kk=tree5[no].find(-(*tree2[no].begin()).b);
tree5[no].erase(kk);
//auto k=tree2[no].find((*tree2[no].end()));
tree2[no].erase(tree2[no].begin());
}
else{
break;
}
}
/*for(auto j:tree2[no]){
cout<<j.a.a<<","<<j.a.b<<","<<j.b<<endl;
}*/
if(tree3[no].size()){
/* auto j=tree3[no].end();
j--;*/
tree[no]=max(tree[no],abs((-(*tree5[no].begin()))-val));
tree[no]=max(tree[no],abs((*tree3[no].begin())-val));
}
}
void build(llo no,llo l,llo r){
tree[no]=-1;
if(l==r){
tree4[no].pb({{l-aa[l].b,l-aa[l].a},it[l]});
// cout<<l<<","<<l-aa[l].b<<','<<l-aa[l].a<<','<<it[l]<<endl;
}
else{
llo mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree4[no]=tree4[no*2+1];
for(auto j:tree4[no*2+2]){
tree4[no].pb(j);
}
sort(tree4[no].begin(),tree4[no].end(),cmp);
}
/* cout<<l<<",,"<<r<<endl;
for(auto j:tree4[no]){
cout<<j.a.a<<" "<<j.a.b<<" "<<j.b<<endl;
}*/
pollo[no]=(llo)(tree4[no].size())-1;
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo le,llo val){
for(llo i=0;i<lazy[no].size();i++){
push(no,lazy[no][i].a,lazy[no][i].b);
if(l<r){
lazy[no*2+1].pb(lazy[no][i]);
}
}
lazy[no].clear();
if(bb<l or aa>r or l>r){
return;
}
if(aa<=l and r<=bb){
// cout<<l<<" "<<r<<" "<<le<<" "<<val<<endl;
push(no,le,val);
if(l<r){
lazy[no*2+1].pb({le,val});
}
}
else{
llo mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,le,val);
update(no*2+2,mid+1,r,aa,bb,le,val);
tree[no]=max(tree[no*2+1],tree[no*2+2]);
}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
for(llo i=0;i<lazy[no].size();i++){
push(no,lazy[no][i].a,lazy[no][i].b);
if(l<r){
lazy[no*2+1].pb(lazy[no][i]);
}
}
lazy[no].clear();
if(bb<l or aa>r or l>r){
return -1;
}
if(aa<=l and r<=bb){
return tree[no];
}
else{
llo mid=(l+r)/2;
llo x=query(no*2+1,l,mid,aa,bb);
llo y=query(no*2+2,mid+1,r,aa,bb);
tree[no]=max(tree[no*2+1],tree[no*2+2]);
return max(x,y);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i]>>aa[i].a>>aa[i].b;
}
llo q;
cin>>q;
for(llo i=0;i<q;i++){
llo bb,cc;
cin>>bb>>cc;
pre[bb-1].pb({cc-1,i});
}
build(0,0,n-1);
for(llo i=n-1;i>=0;i--){
if(aa[i].a+i<n){
update(0,0,n-1,aa[i].a+i,min(aa[i].b+i,n-1),i,it[i]);
// cout<<i<<"::"<<aa[i].a+i<<","<<min(aa[i].b+i,n-1)<<endl;
}
for(auto j:pre[i]){
ans[j.b]=query(0,0,n-1,i,j.a);
}
}
for(llo i=0;i<q;i++){
cout<<ans[i]<<endl;
}
return 0;
}
Compilation message
antennas.cpp: In function 'void update(llo, llo, llo, llo, llo, llo, llo)':
antennas.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo i=0;i<lazy[no].size();i++){
~^~~~~~~~~~~~~~~~
antennas.cpp: In function 'llo query(llo, llo, llo, llo, llo)':
antennas.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo i=0;i<lazy[no].size();i++){
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
155384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
155384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3100 ms |
372408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
155384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
