oj.uz

Submission #328188

# Submission time Handle Problem Language Result Execution time Memory
328188 2020-11-15T15:59:37 Z nickmet2004 Triple Jump (JOI19_jumps) C++11
0 / 100
 185 ms 37228 KB 
#include<bits/stdc++.h>

using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
int n , q , a[N] , ans[N];
vector<ipair> Q[N];
vector<int> e[N];

void R(){
    stack<int> s;
    for(int i = 1; i <= n; ++i){
        while(!s.empty() && a[i] >= a[s.top()]) e[s.top()].emplace_back(i) , s.pop();
        if(!s.empty()) e[s.top()].emplace_back(i);
        s.push(i);
    }
}
struct Node{
    int mx , f , a;
    Node(int mx =0 , int f = 0 , int a = 0) : mx(mx) , f(f) ,a(a) {}
}T[1<<19];
Node operator+(const Node &A , const Node &B){
    Node ret;
    ret.mx = max({A.mx , A.f + B.a , B.mx});
    ret.a = max(A.a , B.a);
    ret.f = max(A.f , B.f);
    return ret;
}
void B(int l = 1 , int r= n  , int pos = 1){
    if(l == r){
        T[pos].a = a[l]; return;
    }
    int mid = (l + r)>>1;
    B(l , mid , pos *  2 ); B(mid + 1 ,r , pos * 2 + 1);
    T[pos].a = max(T[pos* 2].a , T[pos * 2 + 1].a);
}
void upd(int i , int x , int l = 1 , int r = n  , int pos = 1){
    //if(i < l || i > r)return;
    if(l == r){
        T[pos].f = max(T[pos].f , x);
        T[pos].mx = T[pos].f + T[pos].a;
        //T[pos].mx = max(T[pos].mx , x + T[pos].a);
        return;
    }
    int mid = (l + r)>>1;
    if(i <= mid) upd(i ,x , l ,mid,  pos * 2);
    else upd(i ,x , mid +1 , r, pos * 2 + 1);
    T[pos] = T[pos * 2 ] + T[pos * 2 + 1];
}
Node get(int L ,int R , int l = 1 , int r= n  , int pos = 1){
    if(r < L || R < l)return Node();
    if(L <= l && r <= R) return T[pos];
    int mid = (l + r)>>1;
    return get(L , R , l , mid , pos * 2 ) + get(L , R ,mid + 1 , r , pos * 2 + 1);
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i =1; i <= n; ++i)cin >> a[i];
    cin >> q;
    for(int i = 0; i < q; ++i){
        int l , r; cin >> l >> r;
        Q[l].emplace_back(r , i);
    }//cerr<<endl;
    R();
    B();
    //for(auto x : e)cout << x.first << " " << x.second << endl;
    for(int l = n; l; --l){
        for(int x : e[l])if(2 * x - l < n) upd(2 * x - l , a[l] + a[x]);
        for(auto X : Q[l]){
            int i = X.second , r = X.first;
            ans[i] = get(l , r).mx;
        }
    }
    for(int i= 0; i < q; ++i)cout << ans[i] << " ";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 29932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 29932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 37228 KB Output is correct
2 Incorrect 117 ms 36992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 29932 KB Output isn't correct
2 Halted 0 ms 0 KB -