Submission #969881

#	Time	Username	Problem	Language	Result	Execution time	Memory
969881		VinhLuu	Triple Jump (JOI19_jumps)	C++17	100 / 100	776 ms	81764 KiB

jumps

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<ll,ll> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
//const int mod = 1e9 + 7;
const ll oo = 5e18;

int n, a[N], T[N << 2], lz[N << 2], q, kq[N], val[N << 2];

void build(int i,int l,int r){
    if(l == r){
        val[i] = T[i] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(i << 1, l, mid);
    build(i << 1|1, mid + 1, r);
    val[i] = T[i] = max(T[i << 1], T[i << 1|1]);
}

void update(int i,int l,int r,int u,int v, int x){
    if(l > r || l > v || r < u) return;
    if(u <= l && r <= v){
        val[i] = max(val[i], T[i] + x);
        lz[i] = max(lz[i], x);
        return;
    }
    if(lz[i]){
        val[i << 1] = max(val[i << 1], T[i << 1] + lz[i]);
        val[i << 1|1] = max(val[i << 1|1], T[i << 1|1] + lz[i]);
        lz[i << 1] = max(lz[i << 1], lz[i]);
        lz[i << 1|1] = max(lz[i << 1|1], lz[i]);
        lz[i] = 0;
    }
    int mid = (l + r) / 2;
    update(i << 1, l, mid, u, v, x);
    update(i << 1|1, mid + 1, r, u, v, x);
    val[i] = max(val[i << 1], val[i << 1|1]);
}

int get(int i,int l,int r,int u,int v){
    if(l > r || l > v || r < u) return 0;
    if(u <= l && r <= v) return val[i];
    if(lz[i]){
        val[i << 1] = max(val[i << 1], T[i << 1] + lz[i]);
        val[i << 1|1] = max(val[i << 1|1], T[i << 1|1] + lz[i]);
        lz[i << 1] = max(lz[i << 1], lz[i]);
        lz[i << 1|1] = max(lz[i << 1|1], lz[i]);
        lz[i] = 0;
    }
    int mid = (l + r) / 2;
    return max(get(i << 1, l, mid, u, v), get(i << 1|1, mid + 1, r, u, v));
}


#define lpv
#ifdef lpv

vector<pii> vr[N];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    cin >> q;
    for(int i = 1; i <= q; i ++){
        int l, r; cin >> l >> r;
        vr[l].pb({r, i});
    }
    stack<int> st;
    build(1, 1, n);
    st.push(n);
    for(int i = n - 1; i >= 1; i --){
        if(i + 2 <= n) update(1, 1, n, i + 2, n, a[i] + a[i + 1]);
        while(!st.empty() && a[i] >= a[st.top()]){
            int tmp = st.top() - i;
            if(st.top() + tmp <= n) update(1, 1, n, st.top() + tmp, n, a[i] + a[st.top()]);
            st.pop();
        }
        if(!st.empty()){
            int tmp = st.top() - i;
            if(st.top() + tmp <= n) update(1, 1, n, st.top() + tmp, n, a[i] + a[st.top()]);
        }
        st.push(i);
        for(auto [j, id] : vr[i]) kq[id] = get(1, 1, n, i + 2, j);

    }
    for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
}

#endif // lpv

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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