제출 #1195977

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

jumps

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
struct st{
    vector<pair<ll,ll>> cad;
    vector<ll> cad2;
    void update(ll node, ll l, ll r, ll v)
    {
        if(v>cad[node].y)
        {
            cad[node].x=max(cad2[node]+v,cad[node].x);
            cad[node].y=v;
        }
    }
    void propagate(ll node, ll l, ll r)
    {
        if(cad[node].y!=0)
        {
            ll m=(l+r)/2;
            update(node*2,l,m, cad[node].y);
            update(node*2+1,m+1,r, cad[node].y);
            cad[node].y=0;
        }
    }
    void update(ll node, ll l, ll r, ll a, ll b, ll v)
    {
        if(l>b||r<a) return ;
        if(l>=a&&r<=b) {update(node, l, r, v); return;}
        propagate(node, l, r);
        ll m=(l+r)/2;
        update(node*2, l, m, a, b, v);
        update(node*2+ 1, m+1, r, a, b, v);
        cad[node].x=max(cad[node*2].x,cad[node*2+1].x);
    }
    void update(ll a, ll b, ll v) {if(b<a) return; update(1, 1, n, a, b, v);}
    void update(ll a, ll v) {update(a,a,v);}

    ll query(ll node, ll l, ll r, ll a, ll b)
    {
        if(l>b||r<a) return 0;
        if(l>=a&&r<=b) return cad[node].x;
        propagate(node, l, r);
        ll m=(l+r)/2;
        return max(query(node*2, l, m, a, b) , query(node*2+ 1, m+1, r, a, b));
    }
    ll query(ll a, ll b) {if(b<a) return 0;return query(1, 1, n, a, b);}
    ll query(ll a) {return query(a,a);}
    ll n=1;
    st(ll N,vector<ll> asd)
    {
        while(n<=N) n*=2;
        cad.resize(n*2);
        cad2.resize(n*2);
        for(int i=1; i<asd.size(); i++)
            cad2[i+n-1]=asd[i];
        for(int i=n-1; i>0; i--)
            cad2[i]=max(cad2[i*2],cad2[i*2+1]);
    }
};
int main()
{
    ll n;
    cin>>n;
    vector<ll> cad(n+1);
    for(int i=1; i<=n; i++)
        cin>>cad[i];
    cad[0]=1e9;
    st asd(n,cad);
    vector<vector<ll>> p(n+2);
    vector<vector<pair<ll,ll>>> c(n+2);
    stack<ll> q;q.push(0); 
    for(int i=1; i<=n; i++)
    {
        while(cad[q.top()]<=cad[i])
        {
            p[q.top()].push_back(i);
            q.pop();
        }
        p[q.top()].push_back(i);
        q.push(i);
    }
    
    ll qu;
    cin>>qu;
    vector<ll> ans(qu);
    for(int i=0; i<qu; i++)
    {
        ll a,b;
        cin>>a>>b;
        c[a].push_back({i,b});
    }
    for(int i=n; i>0; i--)
    {
        for(auto j:p[i]) asd.update(j*2-i,n,cad[i]+cad[j]);
        for(auto j:c[i]) ans[j.x]=asd.query(i,j.y);
    }
    for(auto i:ans) cout<<i<<"\n";
}
/*         5
     5        3 
   5   5    3   0  
  5 2 1 5 3 0 0 0 
         5 
     5       3 
   5   5   3   0 
  5 2 1 5 3 0 0 0 

         9 
     5       9 
   5   5   9   0 
  5 2 1 5 9 0 0 0 

         9 
     8       9
   5   8   9   0 
  5 2 1 8 9 0 0 0 
        15 
     15      10 
   5   15  10   0 
  5 2 1 8 10 0 0 0 */

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