oj.uz

Submission #219531

# Submission time Handle Problem Language Result Execution time Memory
219531 2020-04-05T13:35:26 Z MKopchev Triple Jump (JOI19_jumps) C++14
32 / 100
 4000 ms 33896 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Execution timed out 4070 ms 4984 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 33640 KB Output is correct
2 Correct 60 ms 31468 KB Output is correct
3 Correct 61 ms 31980 KB Output is correct
4 Correct 73 ms 33512 KB Output is correct
5 Correct 73 ms 33512 KB Output is correct
6 Correct 66 ms 33512 KB Output is correct
7 Correct 65 ms 33384 KB Output is correct
8 Correct 65 ms 33388 KB Output is correct
9 Correct 70 ms 33896 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Execution timed out 4070 ms 4984 KB Time limit exceeded
12 Halted 0 ms 0 KB -