oj.uz

Submission #865648

# Submission time Handle Problem Language Result Execution time Memory
865648 2023-10-24T13:01:50 Z prohacker Triple Jump (JOI19_jumps) C++14
19 / 100
 4000 ms 23808 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int N = 2e5+10;
const ll INF = 1e15;
const int mod = 1e9+7;

int n,a[N];
int t;
vector<pair<int,int>> q[N];
stack<int> st;
ll ans[500010],lazy[4*N];

struct Node{
    ll best,mx,Mx;

    Node() {};
    Node(ll _best, ll _mx, ll _Mx) {
        best = _best;
        mx = _mx;
        Mx = _Mx;
    };
}tree[4*N];

Node operator + (Node u, Node v) {
    Node res = u;
    res.best = max({res.best,u.mx+v.Mx,v.best});
    res.mx = max(res.mx,v.mx);
    res.Mx = max(res.Mx,v.Mx);
    return res;
}

void build(int id = 1, int l = 1, int r = n) {
    if(l == r) {
        tree[id].Mx = a[l];
        tree[id].best = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(id << 1,l,mid);
    build(id << 1 | 1,mid+1,r);
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

void down(int id, int l, int r) {
    ll t = lazy[id];
    if(t == 0) {
        return;
    }
    tree[id].mx = max(tree[id].mx,t);
    tree[id].best = max(-INF,tree[id].mx+tree[id].Mx);
    if(l < r) {
        lazy[id << 1] = max(lazy[id << 1],t);
        lazy[id << 1 | 1] = max(lazy[id << 1 | 1],t);
    }
    t = 0;
}

void update(int u, int v, ll val, int id = 1, int l = 1, int r = n) {
    down(id,l,r);
    if(u > v || l > r || r < u || v < l) {
        return;
    }
    if(l == r) {
        lazy[id] = val;
        down(id,l,r);
        return;
    }
    int mid = l + r >> 1;
    if(u <= mid) {
        update(u,v,val,id << 1,l,mid);
    }
    if(mid+1 <= v) {
        update(u,v,val,id << 1 | 1,mid+1,r);
    }
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

Node get(int u, int v, int id = 1, int l = 1, int r = n) {
    if(u > v || l > r || r < u || v < l) {
        return {-INF,-INF,-INF};
    }
    if(u <= l && r <= v) {
        return tree[id];
    }
    int mid = l + r >> 1;
    return get(u,v,id << 1,l,mid)+get(u,v,id << 1 | 1,mid+1,r);
}

signed main()
{
    if (fopen("triplejump.inp", "r")) {
        freopen("triplejump.inp", "r", stdin);
        freopen("triplejump.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    cin >> t;
    for(int i = 1 ; i <= t ; i++) {
        int l,r; cin >> l >> r;
        q[l].push_back({r,i});
    }
    build();
    for(int i = n ; i > 0 ; i--) {
        while(!st.empty() && a[st.top()] < a[i]) {
            update(2*st.top()-i,n,a[i]+a[st.top()]);
            st.pop();
        }
        if(!st.empty()) {
            update(2*st.top()-i,n,a[i]+a[st.top()]);
        }
        st.push(i);
        for(auto p:q[i]) {
            ans[p.second] = get(i,p.first).best;
        }
    }
    for(int i = 1 ; i <= t ; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = l + r >> 1;
      |               ~~^~~
jumps.cpp: In function 'void update(int, int, long long int, int, int, int)':
jumps.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid = l + r >> 1;
      |               ~~^~~
jumps.cpp: In function 'Node get(int, int, int, int, int)':
jumps.cpp:89:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int mid = l + r >> 1;
      |               ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("triplejump.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("triplejump.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 735 ms 23688 KB Output is correct
12 Correct 485 ms 23380 KB Output is correct
13 Correct 512 ms 23808 KB Output is correct
14 Correct 727 ms 23476 KB Output is correct
15 Correct 749 ms 23444 KB Output is correct
16 Correct 751 ms 23136 KB Output is correct
17 Correct 732 ms 23124 KB Output is correct
18 Correct 739 ms 22912 KB Output is correct
19 Correct 749 ms 23372 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4006 ms 19104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 735 ms 23688 KB Output is correct
12 Correct 485 ms 23380 KB Output is correct
13 Correct 512 ms 23808 KB Output is correct
14 Correct 727 ms 23476 KB Output is correct
15 Correct 749 ms 23444 KB Output is correct
16 Correct 751 ms 23136 KB Output is correct
17 Correct 732 ms 23124 KB Output is correct
18 Correct 739 ms 22912 KB Output is correct
19 Correct 749 ms 23372 KB Output is correct
20 Execution timed out 4006 ms 19104 KB Time limit exceeded
21 Halted 0 ms 0 KB -