제출 #1261944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261944		nguyenhuythach	3단 점프 (JOI19_jumps)	C++20	100 / 100	843 ms	118208 KiB

jumps

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;

const int nmax=5e5+1;
int n,q;
int a[nmax],ans[nmax];
vector<pii> query[nmax];
vector<int> nxt[nmax];

void input()
{
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    cin >> q;
    FOR(i,1,q)
    {
        int l,r; cin >> l >> r;
        query[l].push_back({r,i});
    }
}

struct SEGTREE
{
    vector<pii> tree;
    vector<int> lazy;
    int n=0;
    
    void build(int id,int l,int r)
    {
        if(l==r)
        {
            tree[id]={a[l],a[l]};
            return;
        }
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        tree[id].fi=max(tree[id*2].fi,tree[id*2+1].fi);
        tree[id].se=max(tree[id*2].se,tree[id*2+1].se);
    }
    
    SEGTREE(int N)
    {
        n=N;
        tree.resize(4*n+5,{0,0});
        lazy.resize(4*n+5,0);
        build(1,1,n);
    }
    
    void down(int id,int l,int r)
    {
        tree[id].fi=max(tree[id].fi,tree[id].se+lazy[id]);
        if(l!=r)
        {
            lazy[id*2]=max(lazy[id*2],lazy[id]);
            lazy[id*2+1]=max(lazy[id*2+1],lazy[id]);
        }
        lazy[id]=0;
    }
    
    void update(int id,int l,int r,int a,int b,int val)
    {
        down(id,l,r);
        if(b<l || r<a) return;
        if(a<=l && r<=b)
        {
            lazy[id]+=val;
            down(id,l,r);
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,a,b,val);
        update(id*2+1,mid+1,r,a,b,val);
        tree[id].fi=max(tree[id*2].fi,tree[id*2+1].fi);
    }
    
    int get(int id,int l,int r,int a,int b)
    {
        down(id,l,r);
        if(b<l || r<a) return 0;
        if(a<=l && r<=b) return tree[id].fi;
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,a,b),get(id*2+1,mid+1,r,a,b));
    }
    
    void update(int l,int r,int val) { update(1,1,n,l,r,val); }
    int get(int l,int r) { return get(1,1,n,l,r); }
};

void buildnxt()
{
    stack<int> s;
    REP(i,n,1)
    {
        if(s.empty()) s.push(i);
        else
        {
            while(a[s.top()]<=a[i])
            {
                nxt[i].push_back(s.top());
                s.pop();
                if(s.empty()) break;
            }
            if(!s.empty()) nxt[i].push_back(s.top());
            s.push(i);
        }
    }
}

void solve()
{
    SEGTREE st(n);
    buildnxt();
//    FOR(i,1,n) {FORD(j,nxt[i]) cout << j << ' '; cout << '\n';}
    REP(i,n,1)
    {
        FORD(j,nxt[i]) if(2*j-i<=n) st.update(2*j-i,n,a[i]+a[j]);
        FORD(j,query[i]) ans[j.se]=st.get(i,j.fi);
    }
    FOR(i,1,q) cout << ans[i] << '\n';
}

signed main()
{
    //freopen("kangaroo.in", "r", stdin);
    //freopen("kangaroo.out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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