Submission #861004

#	Time	Username	Problem	Language	Result	Execution time	Memory
861004		yeediot	Two Antennas (JOI19_antennas)	C++17	0 / 100	133 ms	45052 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];
void modify(int l,int r,int id,int p,int v){
    if(l==r){
        mx[id]=mn[id]=v;
        return;
    }
    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]);
    if(!mn[id*2] or !mn[id*2+1])mn[id]=mn[id*2]?mn[id*2]:mn[id*2+1];
    else mn[id]=min(mn[id*2],mn[id*2+1]);
}
pii query(int l,int r,int id,int ql,int qr){
    if(ql>qr or l>r)return {0,0};
    if(ql<=l and r<=qr){
        return {mx[id],mn[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{
        pii a=query(l,mm,id*2,ql,mm);
        pii b=query(mm+1,r,id*2+1,mm+1,qr);
        return {max(a.F,b.F),min(a.S,b.S)};
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[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[l].pb(i);
        remove2[r].pb(i);
    }
    for(int i=1;i<=n;i++){
        for(auto j:add2[i]){
            nowq.insert(j);
        }
        if(i+a[i]<=n)add[i+a[i]].pb(i);
        if(i+b[i]<=n)remov[i+b[i]].pb(i);
        for(auto j:add[i]){
            modify(1,n,1,j,h[j]);
            //cout<<1<<' '<<i<<' '<<j<<'\n';
        }
        for(auto it=nowq.begin();it!=nowq.end();it++){
            pii q=query(1,n,1,max({1LL,i-b[i],ask[*it].F}),min({n,ask[*it].S,i-a[i]}));
            if(q.F)chmax(ans[*it],abs(q.F-h[i]));
            if(q.S)chmax(ans[*it],abs(h[i]-q.S));
        }
        for(auto j:remov[i]){
            modify(1,n,1,j,0);
            //cout<<-1<<' '<<i<<' '<<j<<'\n';
        }
        for(auto j:remove2[i]){
            nowq.erase(j);
        }
    }
    for(int i=1;i<=q;i++){
        //if(!ans[i])cout<<-1<<'\n';
        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 modify(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mm=l+r>>1;
      |            ~^~
antennas.cpp: In function 'std::pair<long long int, long long int> query(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mm=l+r>>1;
      |            ~^~

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