제출 #219517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219517		MKopchev	3단 점프 (JOI19_jumps)	C++14	0 / 100	161 ms	74616 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/*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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54