oj.uz

Submission #1079487

# Submission time Handle Problem Language Result Execution time Memory
1079487 2024-08-28T15:42:46 Z Icelast Global Warming (CEOI18_glo) C++17
0 / 100
 603 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], 1, a[i]-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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 116116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 433 ms 182780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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