oj.uz

Submission #1079493

# Submission time Handle Problem Language Result Execution time Memory
1079493 2024-08-28T15:48:38 Z Icelast Global Warming (CEOI18_glo) C++17
48 / 100
 638 ms 262144 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct PersistentSegmentTree{
    struct Node{
        ll mx = 0;
        int ln = 0, rn = 0;
    };
    int n, N;
    vector<Node> nodes;
    vector<int> ver;
    PersistentSegmentTree(int n): n(n){
        N = n;
        nodes.push_back({0, 0, 0});
        ver.push_back(0);
    };
    void upd(int &node, int ori, int i, int x){
         auto upd = [&](auto upd, int &node, int ori, int low, int high, int i, int x) -> void{
            node = nodes.size();
            nodes.push_back(nodes[ori]);
            if(low == high){
                nodes[node].mx = max(nodes[node].mx, x);
                return;
            }
            int mid = (low+high)/2;
            Node goat = nodes[node];
            if(i <= mid){
                upd(upd, goat.ln, nodes[ori].ln, low, mid, i, x);
            }else{
                upd(upd, goat.rn, nodes[ori].rn, mid+1, high, i, x);
            }
            goat.mx = max(nodes[goat.ln].mx, nodes[goat.rn].mx);
            nodes[node] = goat;
        };
        upd(upd, node, ori, 1, N, i, x);
    }
    int get_max(int node, int l, int r){
        auto get_max = [&](auto get_max, int node, int low, int high, int l, int r) -> int{
            if(low > r || l > high){
                return 0;
            }
            if(low >= l && r >= high){
                return nodes[node].mx;
            }
            int mid = (low+high)/2;
            return max(get_max(get_max, nodes[node].ln, low, mid, l, r), get_max(get_max, nodes[node].rn, mid+1, high, l, r));
        };
        return get_max(get_max, node, 1, N, l, r);
    }
};

void solve(){
    ll n, x;
    ll B = 1e10;
    cin >> n >> x;
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    PersistentSegmentTree Tl(B), Tr(B);
    Tl.ver.resize(n+1, 0);
    Tr.ver.resize(n+1, 0);
    int j = 0;
    for(int i = n; i >= 1; i--){
        j++;
        ll mx = Tr.get_max(Tr.ver[j-1], a[i]+1, B-1)+1;
        Tr.upd(Tr.ver[j], Tr.ver[j-1], a[i], mx);
    }
    j = n;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        j--;
        ll mx = Tl.get_max(Tl.ver[i-1], 1, a[i]-1)+1;
        Tl.upd(Tl.ver[i], Tl.ver[i-1], a[i], mx);
        ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
    }
    cout << ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 400 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 400 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 3532 KB Output is correct
20 Correct 5 ms 3532 KB Output is correct
21 Correct 5 ms 3536 KB Output is correct
22 Correct 5 ms 3532 KB Output is correct
23 Correct 4 ms 3536 KB Output is correct
24 Correct 4 ms 3544 KB Output is correct
25 Correct 4 ms 2260 KB Output is correct
26 Correct 4 ms 3532 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 638 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 116128 KB Output is correct
2 Correct 250 ms 116108 KB Output is correct
3 Correct 248 ms 116084 KB Output is correct
4 Correct 208 ms 116036 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 200 ms 115800 KB Output is correct
7 Correct 212 ms 116052 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 182772 KB Output is correct
2 Correct 462 ms 182804 KB Output is correct
3 Runtime error 609 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 400 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 3532 KB Output is correct
20 Correct 5 ms 3532 KB Output is correct
21 Correct 5 ms 3536 KB Output is correct
22 Correct 5 ms 3532 KB Output is correct
23 Correct 4 ms 3536 KB Output is correct
24 Correct 4 ms 3544 KB Output is correct
25 Correct 4 ms 2260 KB Output is correct
26 Correct 4 ms 3532 KB Output is correct
27 Runtime error 638 ms 262144 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -