답안 #748741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748741 2023-05-26T20:36:08 Z snpmrnhlol 3단 점프 (JOI19_jumps) C++17
0 / 100
154 ms 10576 KB
#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,v3;
int l[N],l2[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();
        }
        while(!v3.empty() && v[v3.top()] >= v[i]){
            l2[v3.top()] = i;v3.pop();
        }
        ///add
        v2.push(i);
        v3.push(i);
    }
    while(!v2.empty()){
        l[v2.top()] = -1;
        v2.pop();
    }
    while(!v3.empty()){
        l2[v3.top()] = -1;
        v3.pop();
    }
    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;
    });
    for(i = 0;i < q;i++){
        while(p >= queries[i].l){
            if(l2[p] != -1 && l2[p] + l2[p] - p <= n - 1)add(l2[p] + l2[p] - p,v[l2[p]] + 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
3
1 15
3 12
11 14
**/

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:70:11: warning: unused variable 'j' [-Wunused-variable]
   70 |     int i,j,q,p;
      |           ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 154 ms 10576 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -