Submission #1038323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038323		phong	Triple Jump (JOI19_jumps)	C++17	27 / 100	107 ms	43868 KiB

jumps

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e9;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int n, a[nmax];
int L[nmax], R[nmax];
int lz[1 << 20];
struct node{
    int first, second, ans;
}tree[1 << 20];
void fix(int id, int val){
    tree[id].se = max(tree[id].se, val);
    lz[id] = max(lz[id], val);
}
void down(int id){
    fix(id << 1, lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
    if(l > v || r < u || u > v) return;
    if(l >= u && r <= v){
        return fix(id, val);
    }
    down(id);
    int mid = r + l >> 1;
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
    tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
}
#define update(l, r, val) update(1, 1, n, l, r, val)
void build(int id, int l, int r){
    if(l == r){
        tree[id].fi = a[l];
        return;
    }
    int mid = r + l >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    tree[id].fi = max(tree[id << 1].fi, tree[id << 1 | 1].fi);
}
int get(int id, int l, int r, int u, int v){
    if(l == r){
        return tree[id].fi + tree[id].se;
    }
    down(id);
    int mid = r + l >> 1;
    if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
    if(mid + 1 > v) return get(id << 1, l, mid, u, v);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
#define get(k) get(1, 1, n, 1, k);
vector<int> adj[nmax];
vector<pii> Q[nmax];
int ans[nmax];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
////    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i){
        L[i] = i - 1;
        while(L[i] > 1 && a[L[i]] < a[i]) L[i] = L[L[i]];
    }
    for(int i = n; i >= 1; --i){
        R[i] = i + 1;
        while(R[i] < n && a[R[i]] <= a[i]) R[i] = R[R[i]];
    }
    for(int i = 1; i <= n; ++i){
        adj[L[i]].push_back(i);
        if(R[i] <= n) adj[i].push_back(R[i]);
    }
    build(1, 1, n);
    int q;
    cin >> q;
    for(int e = 1; e <= q; ++e){
        int l, r;
        cin >> l >> r;
        Q[l].push_back({r, e});
    }
    for(int i = n; i >= 1; --i){
        for(auto p : adj[i]){
            int k = p - i + p;
//            cout <<i<< ' '<< p << ' ' << k << endl;
            update(k, n, a[i] + a[p]);
        }
        for(auto [r, id] : Q[i]){
            ans[id] = get(r);
        }
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] << endl;
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5

4
2 1 5 3
1
1 4


*/

Compilation message (stderr)

jumps.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = r + l >> 1;
      |               ~~^~~
jumps.cpp: In function 'void build(long long int, long long int, long long int)':
jumps.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = r + l >> 1;
      |               ~~^~~
jumps.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = r + l >> 1;
      |               ~~^~~
jumps.cpp: At global scope:
jumps.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main(){
      | ^~~~

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