제출 #1195566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195566		Marco_Escandon	Triple Jump (JOI19_jumps)	C++20	32 / 100	4094 ms	16556 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
struct st
{
    vector<ll> cad;
    ll query(ll a, ll b)
    {
        ll s=0;
        a+=cad.size()/2;
        b+=cad.size()/2;
        while(a<=b)
        {
            if(a%2==1)s=max(s,cad[a++]);
            if(b%2==0)s=max(s,cad[b--]);
            a/=2;
            b/=2;
        }
        return s;
    }
    void update(ll a, ll b)
    {
        a+=cad.size()/2;
        cad[a]=b;
        a/=2;
        while(a>0)
        {
            cad[a]=max(cad[a*2],cad[a*2+1]);
            a/=2;
        }
    }
    st(ll n)
    {
        cad.resize(n*4);
    }
};

int main()
{
    ll n;
    cin>>n;
    st asd(n+2);
    vector<ll> cad(n+1);
    for(int i=1; i<=n; i++)
    {
        cin>>cad[i];
        asd.update(i,cad[i]);
    }
    cad[0]=1e10;
    vector<pair<ll,ll>> p;
    stack<ll> q;q.push(0); 
    for(int i=1; i<=n; i++)
    {
        while(cad[q.top()]<=cad[i])
        {
            p.push_back({q.top(),i});
            q.pop();
        }
        p.push_back({q.top(),i});
        q.push(i);
    }
    ll qu;
    cin>>qu;
    while(qu--)
    {
        ll a, b,ans=0;
        cin>>a>>b;
        for(auto i:p)
        {
            if(a<=i.x&&i.y*2-i.x<=b)
            ans=max(ans,cad[i.x]+cad[i.y]+asd.query(i.y*2-i.x,b));
        }
        cout<<ans<<"\n";
    }
}

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