Submission #279933

#	Time	Username	Problem	Language	Result	Execution time	Memory
279933		MKopchev	Two Antennas (JOI19_antennas)	C++14	13 / 100	3048 ms	25976 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];

void solve()
{
    for(int i=1;i<=n;i++)
    {
        value[i]=-inf;
        mx[i]=-inf;
    }

    for(int i=1;i<=n;i++)
    {
        for(auto k:in[i])
        {
            value[k]=-inp[k];
        }

        for(int j=max(i-b[i],1);j<=i-a[i];j++)
            mx[j]=max(mx[j],inp[i]+value[j]);

        for(auto k:seen[i])
        {
            for(int j=k.first;j<=i;j++)
            {
                outp[k.second]=max(outp[k.second],mx[j]);
            }
        }

        for(auto k:out[i])
        {
            value[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:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
antennas.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |         scanf("%i%i%i",&inp[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
antennas.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%i%i",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

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