제출 #748753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748753		snpmrnhlol	3단 점프 (JOI19_jumps)	C++17	100 / 100	1068 ms	67744 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
const int inf = 1e9;
int v[N];
struct query{
    int l,r,id;
}queries[N];
stack <int> v2;
int l[N];
vector <int> upd[N];
int ans[N];
int n;
struct nod{
    int maxx,maxx2,ans;
}seg[4*N];
nod operator+(nod a,nod b){
    return {max(a.maxx,b.maxx),max(a.maxx2,b.maxx2),max(max(a.ans,b.ans),a.maxx2 + b.maxx)};
}
void build(int l,int r,int node = 1){
    if(l == r){
        seg[node] = {v[l],-inf,-inf};
    }else{
        int mij = (l + r)/2;
        build(l,mij,node*2);
        build(mij + 1,r,node*2 + 1);
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
}
void add(int pos,int val,int l = 0,int r = n - 1,int node = 1){
    //if(l == 0 && r == n - 1)cout<<pos<<' '<<val<<'\n';
    if(l == r){
        seg[node].maxx2 = max(seg[node].maxx2,val);
        seg[node].ans = max(seg[node].maxx + seg[node].maxx2,seg[node].ans);
    }else{
        int mij = (l + r)/2;
        if(pos <= mij){
            add(pos,val,l,mij,node*2);
        }else{
            add(pos,val,mij + 1,r,node*2 + 1);
        }
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
}
nod get(int ql,int qr,int l = 0,int r = n - 1,int node = 1){
    //if(l == 0 && r == n - 1)cout<<ql<<' '<<qr<<'\n';
    if(ql <= l && r <= qr){
        //cout<<node<<' '<<seg[node].maxx<<' '<<seg[node].maxx2<<' '<<seg[node].ans<<'\n';
        return seg[node];
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            return get(ql,qr,l,mij,node*2);
        }else if(mij < ql){
            return get(ql,qr,mij + 1,r,node*2 + 1);
        }else{
            return get(ql,mij,l,mij,node*2) + get(mij + 1,qr,mij + 1,r,node*2 + 1);
        }
    }
}
void display(int l = 0,int r = n - 1,int node = 1){
    if(l != r){
        int mij = (l + r)/2;
        display(l,mij,node*2);
        display(mij + 1,r,node*2 + 1);
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
    cout<<l<<' '<<r<<' '<<seg[node].maxx<<' '<<seg[node].maxx2<<' '<<seg[node].ans<<'\n';
}
int main(){
    int i,j,q,p;
    cin>>n;p = n - 1;
    for(i = 0;i < n;i++)cin>>v[i];
    build(0,n - 1);
    //display();
    for(i = 0;i < n;i++){
        ///check
        while(!v2.empty() && v[v2.top()] <= v[i]){
            l[v2.top()] = i;v2.pop();
        }
        ///add
        v2.push(i);
    }
    while(!v2.empty()){
        l[v2.top()] = -1;
        v2.pop();
    }
    for(i = n - 1;i >= 0;i--){
        while(!v2.empty() && v[v2.top()] <= v[i]){
            upd[i].push_back(v2.top());v2.pop();
            //cout<<i<<' '<<v2.top()<<'\n';
        }
        v2.push(i);
    }
    cin>>q;
    for(i = 0;i < q;i++){
        queries[i].id = i;
        cin>>queries[i].l>>queries[i].r;queries[i].l--;queries[i].r--;
    }
    sort(queries,queries + q,[&](query a,query b){
        return a.l > b.l;
    });
    //add(11,124);
    for(i = 0;i < q;i++){
        while(p >= queries[i].l){
            for(auto x:upd[p]){
                if(x + x - p < n){
                    add(x + x - p,v[x] + v[p]);
                }
            }
            if(l[p] != -1 && l[p] + l[p] -  p <= n - 1)add(l[p] + l[p] - p,v[l[p]] + v[p]);
            p--;
        }
        //display();
        ans[queries[i].id] = get(queries[i].l,queries[i].r).ans;
    }
    for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
    return 0;
}
/**
15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
1
3 12
**/

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

jumps.cpp: In function 'int main()':
jumps.cpp:71:11: warning: unused variable 'j' [-Wunused-variable]
   71 |     int i,j,q,p;
      |           ^

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