Submission #219531

#	Time	Username	Problem	Language	Result	Execution time	Memory
219531		MKopchev	Triple Jump (JOI19_jumps)	C++14	32 / 100	4070 ms	33896 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int nmax=(1<<19)+42,MX=20;
int n,q;

int inp[nmax];

vector< pair<int,int> > start;

pair<int,int> table[20][nmax];

int mem[nmax];

pair<int/*value*/,int/*id*/> take_mx(int l,int r)
{
    int st=mem[r-l+1];
    return max(table[st][l],table[st][r-(1<<st)+1]);
}

int query()
{
    int l,r;

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

    int ret=0;

    for(auto k:start)
    {
        int a=k.first;
        int b=k.second;

        if(l<=a&&b+b-a<=r)
        {
            ret=max(ret,inp[a]+inp[b]+take_mx(b+b-a,r).first);
        }
    }
    return ret;
}

stack<int> active;
int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    for(int i=1;i<=n;i++)
        table[0][i]={inp[i],i};

    for(int st=1;(1<<st)<=n;st++)
        for(int i=1;i+(1<<st)-1<=n;i++)
            table[st][i]=max(table[st-1][i],table[st-1][i+(1<<(st-1))]);

    for(int i=1;i<=n;i++)
    {
        while((1<<(mem[i]+1))<=i)mem[i]++;
    }

    for(int i=1;i<=n;i++)
    {

        while(active.size()&&inp[active.top()]<=inp[i])
        {
            start.push_back({active.top(),i});
            active.pop();
        }

        if(active.size())start.push_back({active.top(),i});

        active.push(i);
    }

    scanf("%i",&q);
    for(int i=1;i<=q;i++)
        printf("%i\n",query());

    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int query()':
jumps.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&l,&r);
     ~~~~~^~~~~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:45:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~
jumps.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54