Submission #911023

#	Time	Username	Problem	Language	Result	Execution time	Memory
911023		StefanSebez	Two Antennas (JOI19_antennas)	C++14	100 / 100	517 ms	37688 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
const int N=2*1e5+50;
const int inf=1e9+1000;
int nc,root,lc[2*N],rc[2*N],maks[2*N],mn[2*N],ans[2*N],lazymn[2*N],lazymaks[2*N];
void update(int c,int R)
{
    if(maks[c]>0) ans[c]=max(ans[c],abs(maks[c]-R));
    if(mn[c]<inf) ans[c]=max(ans[c],abs(mn[c]-R));
    lazymn[c]=min(lazymn[c],R);
    lazymaks[c]=max(lazymaks[c],R);
}
void push(int c)
{
    if(lazymn[c]<inf) update(lc[c],lazymn[c]);
    if(lazymaks[c]>0) update(lc[c],lazymaks[c]);
    if(lazymn[c]<inf) update(rc[c],lazymn[c]);
    if(lazymaks[c]>0) update(rc[c],lazymaks[c]);
    lazymn[c]=inf;
    lazymaks[c]=0;
}
void Update(int &c,int ss,int se,int qind,int qval)
{
    if(!c)c=++nc;
    if(ss==se)
    {
        maks[c]=mn[c]=qval;
        if(qval==0) mn[c]=inf;
        return;
    }
    push(c);
    int mid=(ss+se)/2;
    if(qind<=mid) Update(lc[c],ss,mid,qind,qval);
    else Update(rc[c],mid+1,se,qind,qval);
    maks[c]=max(maks[lc[c]],maks[rc[c]]);
    mn[c]=min(mn[lc[c]],mn[rc[c]]);
    //ans[c]=max(ans[lc[c]],ans[rc[c]]);
}
void UpdateLazy(int &c,int ss,int se,int qs,int qe,int R)
{
    if(qs<=ss && se<=qe) {update(c,R);return;}
    else if(qe<ss || se<qs) return;
    push(c);
    int mid=(ss+se)/2;
    UpdateLazy(lc[c],ss,mid,qs,qe,R);
    UpdateLazy(rc[c],mid+1,se,qs,qe,R);
    ans[c]=max(ans[lc[c]],ans[rc[c]]);
}
int Get(int c,int ss,int se,int qs,int qe)
{
    if(qs>qe) return 0;
    if(qs<=ss && se<=qe) return ans[c];
    else if(qe<ss || se<qs) return 0;
    push(c);
    int mid=(ss+se)/2;
    return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
int main()
{
    for(int i=0;i<2*N;i++) mn[i]=lazymn[i]=inf;

    int n;scanf("%i",&n);
    int H[n+1],A[n+1],B[n+1];
    vector<int> dodaj[n+1],oduzmi[n+1];
    for(int i=1;i<=n;i++)
    {
        scanf("%i%i%i",&H[i],&A[i],&B[i]);
        if(i+A[i]<=n) dodaj[i+A[i]].pb(i);
        if(i+B[i]+1<=n) oduzmi[i+B[i]+1].pb(i);
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%i:\n",i);
        for(auto j:dodaj[i]) printf("%i ",j);
        printf("\n");
        for(auto j:oduzmi[i]) printf("%i ",j);
        printf("\n");
    }*/
    int q;scanf("%i",&q);
    vector<pair<pair<int,int>,int> >Qs;
    for(int i=1;i<=q;i++)
    {
        int l,r;scanf("%i%i",&l,&r);
        Qs.pb({{r,l},i});
    }
    sort(Qs.begin(),Qs.end());
    int res[q+1];
    for(int i=1,j=0;i<=n;i++)
    {
        int L=i-B[i],R=i-A[i];
        for(auto k:dodaj[i]) Update(root,1,n,k,H[k]);
        for(auto k:oduzmi[i]) Update(root,1,n,k,0);
        UpdateLazy(root,1,n,L,R,H[i]);
        while(j<q && Qs[j].fi.fi==i)
        {
            //printf("%i ",Qs[j].se);
            res[Qs[j].se]=Get(root,1,n,Qs[j].fi.se,Qs[j].fi.fi-1);
            if(res[Qs[j].se]==0) res[Qs[j].se]=-1;
            j++;
        }
    }
    for(int i=1;i<=q;i++) printf("%i\n",res[i]);
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:65:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     int n;scanf("%i",&n);
      |           ~~~~~^~~~~~~~~
antennas.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%i%i%i",&H[i],&A[i],&B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:82:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     int q;scanf("%i",&q);
      |           ~~~~~^~~~~~~~~
antennas.cpp:86:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         int l,r;scanf("%i%i",&l,&r);
      |                 ~~~~~^~~~~~~~~~~~~~

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