Submission #389665

#	Time	Username	Problem	Language	Result	Execution time	Memory
389665		denkendoemeer	Two Antennas (JOI19_antennas)	C++14	100 / 100	822 ms	60964 KiB

antennas

#include<bits/stdc++.h>
#define ll long long
const int inf=1e9;
using namespace std;
int h[200005],a[200005],b[200005],ans[200005],ql[200005],qr[200005],lazy[550000],n;
vector<int>t[400005],t1[400005],t2[400005];
array<int,2>aint[550000];
void upd(int nod,int x)
{
    aint[nod][1]=max(aint[nod][0]+x,aint[nod][1]);
    lazy[nod]=max(lazy[nod],x);
}
void push(int nod)
{
    upd(2*nod,lazy[nod]);
    upd(2*nod+1,lazy[nod]);
    lazy[nod]=-inf;
}
void update1(int nod,int st,int dr,int poz,int val)
{
    if (st==dr){
        aint[nod][0]=val;
        return ;
    }
    push(nod);
    int mij=(st+dr)/2;
    if (poz<=mij)
        update1(nod*2,st,mij,poz,val);
    else
        update1(nod*2+1,mij+1,dr,poz,val);
    aint[nod][0]=max(aint[nod*2][0],aint[nod*2+1][0]);
    aint[nod][1]=max(aint[nod*2][1],aint[nod*2+1][1]);
}
void update2(int nod,int st,int dr,int l,int r,int val)
{
    if (l<=st && dr<=r){
        upd(nod,val);
        return ;
    }
    int mij=(st+dr)/2;
    push(nod);
    if (l<=mij)
        update2(nod*2,st,mij,l,r,val);
    if (mij+1<=r)
        update2(nod*2+1,mij+1,dr,l,r,val);
    aint[nod][0]=max(aint[nod*2][0],aint[nod*2+1][0]);
    aint[nod][1]=max(aint[nod*2][1],aint[nod*2+1][1]);
}
int query(int nod,int st,int dr,int poz)
{
    if (poz<=st)
        return aint[nod][1];
    int mij=(st+dr)/2;
    push(nod);
    if (poz<=mij)
        return max(query(nod*2,st,mij,poz),query(nod*2+1,mij+1,dr,poz));
    else
        return query(nod*2+1,mij+1,dr,poz);
}
void calc()
{
    int i;
    for(i=0;i<550000;i++)
        aint[i][0]=aint[i][1]=lazy[i]=-inf-2;
    for(i=0;i<n;i++){
        for(auto it:t1[i])
            update1(1,0,n-1,it,-h[it]);
        if (i-a[i]>=0)
            update2(1,0,n-1,max(i-b[i],0),i-a[i],h[i]);
        for(auto it:t[i])
            ans[it]=max(query(1,0,n-1,ql[it]),ans[it]);
        for(auto it:t2[i])
            update1(1,0,n-1,it,-inf);
    }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d%d",&h[i],&a[i],&b[i]);
        t1[i+a[i]].push_back(i);
        t2[i+b[i]].push_back(i);
    }
    int q;
    scanf("%d",&q);
    memset(ans,-1,sizeof(ans));
    for(i=0;i<q;i++){
        scanf("%d%d",&ql[i],&qr[i]);
        ql[i]--;
        qr[i]--;
        t[qr[i]].push_back(i);
    }
    calc();
    for(i=0;i<n;i++)
        h[i]=-h[i];
    calc();
    for(i=0;i<q;i++)
        printf("%d\n",ans[i]);
return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
antennas.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         scanf("%d%d%d",&h[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
antennas.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         scanf("%d%d",&ql[i],&qr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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