oj.uz

Submission #1038329

# Submission time Handle Problem Language Result Execution time Memory
1038329 2024-07-29T16:44:46 Z phong Triple Jump (JOI19_jumps) C++17
27 / 100
 219 ms 48660 KB 
//#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][2], R[nmax][2];
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][0] = i - 1;
        while(L[i][0] > 1 && a[L[i][0]] < a[i]) L[i][0] = L[L[i][0]][0];
         L[i][1] = i - 1;
        while(L[i][1] > 1 && a[L[i][1]] > a[i]) L[i][1] = L[L[i][1]][1];
    }
    for(int i = n; i >= 1; --i){
        R[i][0] = i + 1;
        while(R[i][0] < n && a[R[i][0]] < a[i]) R[i][0] = R[R[i][0]][0];
        R[i][1] = i + 1;
        while(R[i][1] < n && a[R[i][1]] > a[i]) R[i][1] = R[R[i][1]][1];
    }
    for(int i = 1; i <= n; ++i){
        for(int id = 0; id < 2; ++id){
            adj[L[i][id]].push_back(i);
            if(R[i][id] <= n) adj[i].push_back(R[i][id]);
        }
    }
    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 << 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

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.0

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

Subtask #2
0 / 14.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 48468 KB Output is correct
2 Correct 113 ms 48320 KB Output is correct
3 Correct 119 ms 48316 KB Output is correct
4 Correct 177 ms 48608 KB Output is correct
5 Correct 177 ms 48468 KB Output is correct
6 Correct 189 ms 48472 KB Output is correct
7 Correct 182 ms 48660 KB Output is correct
8 Correct 219 ms 48508 KB Output is correct
9 Correct 177 ms 48468 KB Output is correct

Subtask #4
0 / 54.0

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