oj.uz

Submission #219517

# Submission time Handle Problem Language Result Execution time Memory
219517 2020-04-05T13:13:41 Z MKopchev Triple Jump (JOI19_jumps) C++14
0 / 100
 161 ms 74616 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/*value*/,int/*id*/> > tree[nmax*2];

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].push_back({inp[l],l});
        return;
    }

    int av=(l+r)/2;
    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=tree[node*2];
    for(auto k:tree[node*2+1])tree[node].push_back(k);

    sort(tree[node].begin(),tree[node].end());

    reverse(tree[node].begin(),tree[node].end());

    while(tree[node].size()>MX)tree[node].pop_back();
}

vector< pair<int/*value*/,int/*id*/> > possible;

void query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)
    {
        for(auto k:tree[node])possible.push_back(k);
        return;
    }

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

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);

    possible={};
    query(1,1,n,l,r);

    sort(possible.begin(),possible.end());
    reverse(possible.begin(),possible.end());

    while(possible.size()>MX)possible.pop_back();

    int ret=0;

    for(int i=0;i<possible.size();i++)
        for(int j=i+1;j<possible.size();j++)
        {
            int s=possible[i].second;
            int t=possible[j].second;

            if(s>t)swap(s,t);

            int current=0;

            if(s-1>=l)current=max(current,take_mx(max(l,2*s-t),s-1).first);

            if((s+t)/2>s)current=max(current,take_mx(s+1,(s+t)/2).first);

            if(2*t-s<=r)current=max(current,take_mx(2*t-s,r).first);

            current+=possible[i].first+possible[j].first;

            //cout<<s<<" "<<t<<" -> "<<current<<endl;

            ret=max(ret,current);
        }

    return ret;
}
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++)
        for(int j=i;j<=n;j++)
        {
            pair<int,int> is=take_mx(i,j);

            cout<<i<<" "<<j<<" "<<is.first<<" "<<is.second<<endl;
        }
    */

    build(1,1,n);

    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:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<possible.size();i++)
                 ~^~~~~~~~~~~~~~~~
jumps.cpp:72:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i+1;j<possible.size();j++)
                       ~^~~~~~~~~~~~~~~~
jumps.cpp:59: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:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:99: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:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24960 KB Output is correct
2 Correct 20 ms 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 20 ms 25088 KB Output is correct
5 Correct 21 ms 25088 KB Output is correct
6 Correct 20 ms 25088 KB Output is correct
7 Incorrect 20 ms 25088 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24960 KB Output is correct
2 Correct 20 ms 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 20 ms 25088 KB Output is correct
5 Correct 21 ms 25088 KB Output is correct
6 Correct 20 ms 25088 KB Output is correct
7 Incorrect 20 ms 25088 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 74464 KB Output is correct
2 Correct 154 ms 74616 KB Output is correct
3 Correct 136 ms 74432 KB Output is correct
4 Correct 155 ms 74352 KB Output is correct
5 Correct 161 ms 74468 KB Output is correct
6 Incorrect 158 ms 73848 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24960 KB Output is correct
2 Correct 20 ms 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 20 ms 25088 KB Output is correct
5 Correct 21 ms 25088 KB Output is correct
6 Correct 20 ms 25088 KB Output is correct
7 Incorrect 20 ms 25088 KB Output isn't correct
8 Halted 0 ms 0 KB -