Submission #1148924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148924		Issa	Triple Jump (JOI19_jumps)	C++20	100 / 100	1125 ms	87148 KiB

jumps

#include <bits/stdc++.h>
#define isb ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ent "\n"

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 100;
const ll INF = 9223372036854775807;
const int inf = INT_MAX;

int n, m;
ll a[maxn];
ll d[maxn*4];
vector<int> q[maxn];
vector<pair<int, int>> e[maxn];
int t[maxn*4];
int c[maxn*4];
int ans[maxn*4];
int res[maxn];

void build(int v, int tl, int tr){
    if(tl == tr){
        d[v] = a[tl];
    } else{
        int mid = (tl + tr) / 2;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        d[v] = max(d[v*2], d[v*2+1]);
    }
}
int getp(int v, int tl, int tr, int pos, int x){
    if(tr <= pos) return 0;
    if(d[v] < x) return 0;
    if(tl == tr) return tl;
    int mid = (tl + tr) / 2;
    int num = getp(v*2, tl, mid, pos, x);
    if(num != 0) return num;
    return getp(v*2+1, mid+1, tr, pos, x);
}
int getb(int v, int tl, int tr, int pos, int x){
    if(d[v] < x) return 0;
    if(pos <= tl) return 0;
    if(tl == tr) return tr;
    int mid = (tl + tr) / 2;
    int num = getb(v*2+1, mid+1, tr, pos, x);
    if(num != 0) return num;
    return getb(v*2, tl, mid, pos, x);
}

void push(int v){
    if(t[v] == -1) return;
    c[v*2] = t[v];
    c[v*2+1] = t[v];
    ans[v*2] = c[v*2] + d[v*2];
    ans[v*2+1] = c[v*2+1] + d[v*2+1];
    t[v*2] = t[v];
    t[v*2+1] = t[v];
    t[v] = -1;
}

int getf(int v, int tl, int tr, int l, int x){
    if(tl != tr) push(v);
    if(tr < l) return 0;
    if(c[v] < x) return 0;
    if(tl == tr) return tl;
    int mid = (tl + tr) / 2;
    int num = getf(v*2, tl, mid, l, x);
    if(num != 0) return num;
    return getf(v*2+1, mid+1, tr, l, x);
}

void upd(int v, int tl, int tr, int l, int r, int x){
    if(tl != tr) push(v);
    if(tl > r || tr < l) return;
    if(l <= tl && tr <= r){
        c[v] = t[v] = x;
        ans[v] = d[v] + x;
    } else{
        int mid = (tl + tr) / 2;
        upd(v*2, tl, mid, l, r, x);
        upd(v*2+1, mid+1, tr, l, r, x);
        ans[v] = max(ans[v*2], ans[v*2+1]);
        c[v] = max(c[v*2], c[v*2+1]);
    }
}

int get(int v, int tl, int tr, int l, int r){
    if(tl != tr) push(v);
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return ans[v];
    int mid = (tl + tr) / 2;
    return max(get(v*2, tl, mid, l, r), get(v*2+1, mid+1, tr, l, r));
}

void asd(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        int j = getp(1, 1, n, i, a[i]);
        int k = getb(1, 1, n, i, a[i]);
        if(i + 2 <= n && j*2-i <= n && j != 0){
            q[i].push_back(j);
        }
        if(i > 1 && 2*i-k <= n && k != 0){
            q[k].push_back(i);
        }
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        e[l].push_back({r, i});
    }
    for(int i = n; i; i--){
        for(int x: q[i]){
            int tl = x*2-i;
            int tr = getf(1, 1, n, tl, a[i] + a[x]);
            if(c[1] < a[i] + a[x]) tr = n+1;
            if(tr != 0) upd(1, 1, n, tl, tr-1, a[i] + a[x]);
        }
        for(auto x: e[i]){
            res[x.second] = get(1, 1, n, i, x.first);
        }
    }
    for(int i = 1; i <= m; i++){
        cout << res[i] << ent;
    }
}

int main(){
    isb;
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++) asd(), cout << ent;
}

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