oj.uz

Submission #328187

# Submission time Handle Problem Language Result Execution time Memory
328187 2020-11-15T15:24:50 Z nickmet2004 Triple Jump (JOI19_jumps) C++11
0 / 100
 183 ms 23208 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] , e;

void R(){
    stack<int> s;
    for(int i = 0; i < n; ++i){
        while(!s.empty() && a[i] >= a[s.top()]) e.emplace_back(s.top() , i) , s.pop();
        if(!s.empty()) e.emplace_back(s.top() , i);
        s.push(i);
    }
}
struct Node{
    int mx , f , 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 = 0 , int r= n - 1 , int pos = 0){
    if(l == r){
        T[pos].a = a[l]; return;
    }
    int mid = (l + r)>>1;
    B(l , mid , pos *  2 + 1); B(mid + 1 ,r , pos * 2 + 2);
    T[pos].a = max(T[pos* 2+ 1].a , T[pos * 2 + 2].a);
}
void upd(int i , int x , int l = 0 , int r = n - 1 , int pos = 0){
    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 + 1);
    else upd(i ,x , mid +1 , r, pos * 2 + 2);
    T[pos] = T[pos * 2 + 1] + T[pos * 2 + 2];
}
Node get(int L ,int R , int l = 0 , int r= n - 1 , int pos = 0){
    if(r < L || R < l)return {0 , 0 ,0};
    if(L <= l && r <= R) return T[pos];
    int mid = (l + r)>>1;
    return get(L , R , l , mid , pos * 2 + 1) + get(L , R ,mid + 1 , r , pos * 2 + 2);
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i =0; i < n; ++i)cin >> a[i];
    cin >> q;
    for(int i = 0; i < q; ++i){
        int l , r; cin >> l >> r; --l; --r;
        Q[l].emplace_back(r , i);
    }//cerr<<endl;
    R();
    B();
    sort(e.rbegin() , e.rend());
    //for(auto x : e)cout << x.first << " " << x.second << endl;
    int P = -1;
    for(int l = n - 1; ~l; --l){
        while(P + 1 < e.size() && e[P + 1].first >= l){
            P++;
            int A = e[P].first , B = e[P].second;
            int Z = 2 * B - A;
            //if(l == 3)cout << a[A] + a[B]<<"a+b"<<endl;
            if(Z < n)upd(Z , a[A] + a[B]);
        }
        //cout << T[6].mx << " T6mx"<<endl;
        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] << " ";
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(P + 1 < e.size() && e[P + 1].first >= l){
      |               ~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Incorrect 9 ms 12140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Incorrect 9 ms 12140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 22496 KB Output is correct
2 Correct 100 ms 22500 KB Output is correct
3 Incorrect 105 ms 23208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Incorrect 9 ms 12140 KB Output isn't correct
3 Halted 0 ms 0 KB -