Submission #328173

#	Time	Username	Problem	Language	Result	Execution time	Memory
328173		nickmet2004	Triple Jump (JOI19_jumps)	C++11	0 / 100	241 ms	44380 KiB

jumps

#include<bits/stdc++.h>
#define f first
#define s second
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;
struct Node{
    int mx, f, a;
};
Node T[N];
/// merge values i * 2 + 1 , i * 2 + 2
Node operator+(const Node&A , const Node&B){
    Node ret = A;
    ret.mx = max({ret.mx , ret.f + B.a,  B.mx});
    ret.a = max(ret.a , B.a);
    ret.f = max(ret.f , B.f);
    return ret;
}
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);
    }
}
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(i < l || i > r)return;
    if(l == r){
        T[pos].f = max(x , T[pos].f);
        return;
    }
    int mid = (l + r) >> 1;
    upd(i , x , l , mid , pos * 2 + 1);
    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(l > R || r < L) return {-1 , -1 , -1};
    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);
    }
    R();
    B();
    sort(e.rbegin() , e.rend());
    //for(auto x : e)cout << x.f << " " << x.s << 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(Z < n) upd(Z , a[A] + a[B]);
        }
        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] <<  " ";
return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:69: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]
   69 |         while(P + 1 < e.size() && e[P + 1].first >= l){
      |               ~~~~~~^~~~~~~~~~

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