oj.uz

Submission #211256

# Submission time Handle Problem Language Result Execution time Memory
211256 2020-03-19T19:24:10 Z brcode Two Antennas (JOI19_antennas) C++14
22 / 100
 676 ms 41208 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5+5;
long long seg[4*MAXN];
long long temph[4*MAXN];
long long n,q;
long long lazy[4*MAXN];
long long h[MAXN];
long long a[MAXN];
long long ans[MAXN];
long long b[MAXN];
vector<int> add[MAXN];
vector<int> rem[MAXN];
vector<pair<int,int>> v1[MAXN];
bool nxt = false;
void build(long long curr,long long l,long long r){
    if(l==r){
        seg[curr] =-987654321987654321;
        lazy[curr] =-987654321987654321;
        temph[curr] = 987654321987654321;
        return;
    }
    long long mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
    lazy[curr] = max(lazy[2*curr],lazy[2*curr+1]);
    temph[curr] = min(temph[2*curr],temph[2*curr+1]);
}
void pushdown(long long curr,long long l,long long r){
    lazy[2*curr] = max(lazy[curr],lazy[2*curr]);
    lazy[2*curr+1] = max(lazy[curr],lazy[2*curr+1]);
    seg[2*curr] = max(seg[2*curr],lazy[2*curr]-temph[2*curr]);
    seg[2*curr+1] = max(seg[2*curr+1],lazy[2*curr+1]-temph[2*curr+1]);
    lazy[curr] = -987654321987654321;
}
void pointupdate(long long curr,long long l,long long r,long long ind,long long x){
    if(l==r){
        temph[curr] = x;
        lazy[curr] = -987654321987654321;
        return;
    }
    pushdown(curr,l,r);
    long long mid = (l+r)/2;
    if(ind<=mid){
        pointupdate(2*curr,l,mid,ind,x);
    }else{
        pointupdate(2*curr+1,mid+1,r,ind,x);
    }
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
    temph[curr] = min(temph[2*curr],temph[2*curr+1]);
    if(curr == 4){
        //cout<<ind<<" "<<x<<" "<<temph[curr]<<" "<<temph[2*curr]<<" "<<temph[2*curr+1]<<endl;
    }
}
void rangeupdate(long long curr,long long l,long long r,long long tl,long long tr,long long val){
    if(l>tr||r<tl){
        return;
    }
    if(tl<=l && r<=tr){
        lazy[curr] = max(lazy[curr],val);
        seg[curr] = max(seg[curr],val-temph[curr]);
       // cout<<curr<<" "<<123<<" "<<l<<" "<<r<<" "<<temph[2*2*curr]<<endl;
        return;
    }
    long long mid =(l+r)/2;
    pushdown(curr,l,r);
    rangeupdate(2*curr,l,mid,tl,tr,val);
    rangeupdate(2*curr+1,mid+1,r,tl,tr,val);
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
}
long long query(long long curr,long long l,long long r,long long tl,long long tr){
  //  cout<<l<<" "<<r<<endl;
    if(l>tr||r<tl){
        return -987654321987654321;
    }
   
    
    if(tl<=l &&r<=tr){
        return seg[curr];
    }
    pushdown(curr,l,r);
    long long mid = (l+r)/2;
    return max(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
int main(){
 
    cin>>n;
    for(long long i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
       if(a[i]+i<MAXN){
            add[a[i]+i].push_back(i);
       }
       if(b[i]+i+1<MAXN){
            rem[b[i]+i+1].push_back(i);
       }
       //cout<<a[i]+i<<" "<<b[i]+i+1<<endl;
       ans[i] = -1;
    }
    
    cin>>q;
    for(long long i=1;i<=q;i++){
        long long l,r;
        cin>>l>>r;
        v1[r].push_back(make_pair(l,i));
    }
    build(1,1,n);
    // cout<<query(1,1,n,1,2)<<endl;
    for(long long i=1;i<=n;i++){
        
        for(long long x:add[i]){
            
            pointupdate(1,1,n,x,h[x]);
            
        }
        for(long long x:rem[i]){
            
            pointupdate(1,1,n,x,987654321987654321);
        }
        //cout<<123<<endl;
        if(i-a[i]>=1){
            rangeupdate(1,1,n,max((long long)1,i-b[i]),i-a[i],h[i]);
          //  cout<<" "<<max((long long)1,i-b[i])<<" "<<i-a[i]<<" "<<h[i]<<endl;
        }
        for(auto x:v1[i]){
             //
            ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
           // cout<<x.first<<" "<<i<<" "<<query(1,1,n,x.first,i)<<endl;
        }
       // cout<<query(1,1,n,1,20)<<endl;
    } 
   
    //reverse
    
//cout<<ans[1]<<endl;
    build(1,1,n);
   // cout<<query(1,1,n,1,2)<<endl;
    for(long long i=1;i<=n;i++){
        h[i] = 1000000000-h[i];
    }
    nxt = true;
     for(long long i=1;i<=n;i++){
        
        for(long long x:add[i]){
           // cout<<h[x]<<endl;
            pointupdate(1,1,n,x,h[x]);
            
        }
        for(long long x:rem[i]){
            
            pointupdate(1,1,n,x,987654321987654321);
        }
        //cout<<123<<endl;
        if(i-a[i]>=1){
            rangeupdate(1,1,n,max((long long)1,i-b[i]),i-a[i],h[i]);
            //cout<<" "<<max(1,i-b[i])<<" "<<i-a[i]<<endl;
        }
        for(auto x:v1[i]){
           // cout<<ans[x.second]<<endl;
            ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
          //  cout<<x.first<<" "<<i<<" "<<query(1,1,n,x.first,i)<<endl;
        }
        
    } 
    /*for(long long i=n;i>=1;i--){
        for(long long x:rem[i+1]){
            
            pointupdate(1,1,n,x,h[x]);
        }
        for(long long x:add[i+1]){
          
            pointupdate(1,1,n,x,-987654321987654321);
        }
        if(i+a[i]<=n){
            rangeupdate(1,1,n,i+a[i],max(i+b[i],n),h[i]);
        }
        for(auto x:v1[i]){
            ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
        }
        
    } */
    
    for(long long i=1;i<=q;i++){
        cout<<ans[i]<<endl;
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Incorrect 14 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Incorrect 14 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 40440 KB Output is correct
2 Correct 664 ms 41080 KB Output is correct
3 Correct 463 ms 38904 KB Output is correct
4 Correct 648 ms 41160 KB Output is correct
5 Correct 296 ms 29620 KB Output is correct
6 Correct 662 ms 41208 KB Output is correct
7 Correct 577 ms 40176 KB Output is correct
8 Correct 670 ms 41172 KB Output is correct
9 Correct 94 ms 19192 KB Output is correct
10 Correct 676 ms 41208 KB Output is correct
11 Correct 422 ms 32120 KB Output is correct
12 Correct 662 ms 41160 KB Output is correct
13 Correct 480 ms 38688 KB Output is correct
14 Correct 467 ms 38648 KB Output is correct
15 Correct 462 ms 38740 KB Output is correct
16 Correct 444 ms 39160 KB Output is correct
17 Correct 485 ms 38944 KB Output is correct
18 Correct 470 ms 39160 KB Output is correct
19 Correct 482 ms 38484 KB Output is correct
20 Correct 477 ms 38720 KB Output is correct
21 Correct 450 ms 38564 KB Output is correct
22 Correct 467 ms 38976 KB Output is correct
23 Correct 475 ms 38772 KB Output is correct
24 Correct 443 ms 38776 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Incorrect 14 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -