Submission #861062

#	Time	Username	Problem	Language	Result	Execution time	Memory
861062		yeediot	Two Antennas (JOI19_antennas)	C++17	100 / 100	564 ms	63828 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
const int mxn=2e5+5;
vector<pii>ask(mxn);
vector<int>add2[mxn];
vector<int>remove2[mxn];
vector<int>add[mxn];
vector<int>remov[mxn];
vector<int>h(mxn),a(mxn),b(mxn),ans(mxn);
set<int>nowq;
int mx[4*mxn],mn[4*mxn],val[4*mxn],tag[4*mxn];
void clear(int l,int r,int id){
    if(l==r){
        mx[id]=-8e18;
        mn[id]=-8e18;
        val[id]=-8e18;
        return;
    }
    int mm=l+r>>1;
    clear(l,mm,id*2);
    clear(mm+1,r,id*2+1);
    mx[id]=-8e18;
    mn[id]=-8e18;
    val[id]=-8e18;
}
void upd(int id,int v){
    chmax(mn[id],v);
    val[id]=max(val[id],mn[id]+mx[id]);
}
void push(int id){
    if(mn[id]==-8e18)return;
    upd(id*2,mn[id]);
    upd(id*2+1,mn[id]);
    mn[id]=-8e18;
}
void modify(int l,int r,int id,int p,int v){
    if(l==r){
        mn[id]=-8e18;
        mx[id]=v;
        return;
    }
    push(id);
    int mm=l+r>>1;
    if(p<=mm) modify(l,mm,id*2,p,v);
    else modify(mm+1,r,id*2+1,p,v);
    mx[id]=max(mx[id*2],mx[id*2+1]);
    val[id]=max(val[id*2],val[id*2+1]);
}
void q_modify(int l,int r,int id,int ql,int qr,int v){
    if(ql>qr)return;
    if(ql<=l and r<=qr){
        upd(id,v);
        return;
    }
    push(id);
    int mm=l+r>>1;
    if(qr<=mm){
        q_modify(l,mm,id*2,ql,qr,v);
    }
    else if(ql>mm){
        q_modify(mm+1,r,id*2+1,ql,qr,v);
    }
    else{
        q_modify(l,mm,id*2,ql,mm,v);
        q_modify(mm+1,r,id*2+1,mm+1,qr,v);
    }
    mx[id]=max(mx[id*2],mx[id*2+1]);
    val[id]=max(val[id*2],val[id*2+1]);
}
int query(int l,int r,int id,int ql,int qr){
    if(ql<=l and r<=qr){
        return val[id];
    }
    push(id);
    int mm=l+r>>1;
    if(qr<=mm){
        return query(l,mm,id*2,ql,qr);
    }
    else if(ql>mm){
        return query(mm+1,r,id*2+1,ql,qr);
    }
    else{
        int a=query(l,mm,id*2,ql,mm);
        int b=query(mm+1,r,id*2+1,mm+1,qr);
        return max(a,b);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int change=0;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
        chmax(change,h[i]);
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        ans[i]=-1;
        int l,r;
        cin>>l>>r;
        ask[i]={l,r};
        add2[r].pb(i);
    }
    clear(1,n,1);
    for(int i=1;i<=n;i++){
        for(auto j:add[i]){
            modify(1,n,1,j,h[j]);
        }
        if(i+a[i]<=n)add[i+a[i]].pb(i);
        if(i+b[i]<=n)remov[i+b[i]].pb(i);
        q_modify(1,n,1,max(i-b[i],1LL),i-a[i],-h[i]);
        for(auto j:add2[i]){
            chmax(ans[j],query(1,n,1,ask[j].F,i));
        }
        for(auto j:remov[i])modify(1,n,1,j,-8e18);
    }
    clear(1,n,1);
    for(int i=1;i<=n;i++){
        h[i]=1e9-h[i]+1;
    }
    for(int i=1;i<=n;i++){
        for(auto j:add[i]){
            modify(1,n,1,j,h[j]);
        }
        q_modify(1,n,1,max(i-b[i],1LL),i-a[i],-h[i]);
        for(auto j:add2[i]){
            chmax(ans[j],query(1,n,1,ask[j].F,i));
        }
        for(auto j:remov[i])modify(1,n,1,j,-8e18);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
 /*
 input:
 
  掃描線
  從1掃到N
  如果當前有詢問
  chmax(ans[j],max(h[i]-min(i-a[i]~i-b[i]),max(i-a[i]~i-b[i]-h[i]));
 */

Compilation message (stderr)

antennas.cpp: In function 'void clear(long long int, long long int, long long int)':
antennas.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mm=l+r>>1;
      |            ~^~
antennas.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mm=l+r>>1;
      |            ~^~
antennas.cpp: In function 'void q_modify(long long int, long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mm=l+r>>1;
      |            ~^~
antennas.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int mm=l+r>>1;
      |            ~^~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65