Submission #1079502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079502		Icelast	Global Warming (CEOI18_glo)	C++17	100 / 100	879 ms	176716 KiB

glo

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct PersistentSegmentTree{
    struct Node{
        int 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){
        if(r > 1e9) r = 1e9;
        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 = 1e9+1;
    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;
    int 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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25