Submission #279988

#	Time	Username	Problem	Language	Result	Execution time	Memory
279988		MKopchev	Two Antennas (JOI19_antennas)	C++14	100 / 100	1522 ms	43516 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42,inf=1e9+42;

int n,q;

int inp[nmax];

int a[nmax],b[nmax];

vector< pair<int/*left*/,int/*id*/> > seen[nmax];

int outp[nmax];

vector<int> in[nmax],out[nmax];

int value[nmax],mx[nmax];

struct info
{
    int max_value,max_mx,max_update;
};

info actual(info ret)
{
    ret.max_mx=max(ret.max_mx,ret.max_value+ret.max_update);
    ret.max_update=-inf;
    return ret;
}
info tree[4*nmax];

void push(int node)
{
    tree[node*2].max_update=max(tree[node*2].max_update,tree[node].max_update);
    tree[node*2+1].max_update=max(tree[node*2+1].max_update,tree[node].max_update);
}

info my_merge(info le,info ri)
{
    le=actual(le);
    ri=actual(ri);

    info ret;
    ret.max_value=max(le.max_value,ri.max_value);
    ret.max_mx=max(le.max_mx,ri.max_mx);
    ret.max_update=-inf;

    return ret;
}
void update_set(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node].max_mx=max(tree[node].max_mx,tree[node].max_value+tree[node].max_update);

        tree[node].max_value=val;

        tree[node].max_update=-inf;

        tree[node].max_mx=max(tree[node].max_mx,tree[node].max_value+tree[node].max_update);

        return;
    }

    push(node);

    int av=(l+r)/2;

    if(pos<=av)update_set(node*2,l,av,pos,val);
    else update_set(node*2+1,av+1,r,pos,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void update_range(int node,int l,int r,int lq,int rq,int val)
{
    if(l==lq&&r==rq)
    {
        tree[node].max_update=max(tree[node].max_update,val);

        tree[node].max_mx=max(tree[node].max_mx,tree[node].max_value+tree[node].max_update);

        return;
    }

    push(node);

    int av=(l+r)/2;

    if(lq<=av)update_range(node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update_range(node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

info query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return actual(tree[node]);

    push(node);

    int av=(l+r)/2;

    info ret;ret.max_mx=-inf;ret.max_value=-inf;ret.max_update=-inf;

    if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);

    return ret;
}

void solve()
{
    for(int i=1;i<=4*n;i++)
    {
        tree[i].max_value=-inf;
        tree[i].max_mx=-inf;
        tree[i].max_update=-inf;
    }

    for(int i=1;i<=n;i++)
    {
        for(auto k:in[i])
        {
            update_set(1,1,n,k,-inp[k]);
        }
        int le=max(i-b[i],1),ri=i-a[i];

        if(le<=ri)update_range(1,1,n,le,ri,inp[i]);

        for(auto k:seen[i])
        {
            outp[k.second]=max(outp[k.second],query(1,1,n,k.first,i).max_mx);
        }

        for(auto k:out[i])
        {
            update_set(1,1,n,k,-inf);
        }

    }
}

int main()
{
    memset(outp,-1,sizeof(outp));

    scanf("%i",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%i%i%i",&inp[i],&a[i],&b[i]);
        if(i+a[i]<=n)in[i+a[i]].push_back(i);
        if(i+b[i]<=n)out[i+b[i]].push_back(i);
    }
    scanf("%i",&q);

    for(int i=1;i<=q;i++)
    {
        int l,r;

        scanf("%i%i",&l,&r);

        seen[r].push_back({l,i});
    }

    solve();

    for(int i=1;i<=n;i++)inp[i]=-inp[i];

    solve();

    for(int i=1;i<=q;i++)
        printf("%i\n",outp[i]);
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
antennas.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |         scanf("%i%i%i",&inp[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
antennas.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |         scanf("%i%i",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

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