Submission #1277763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277763		nanaseyuzuki	Financial Report (JOI21_financial)	C++20	5 / 100	289 ms	18892 KiB

Main

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 3e5 + 5, inf = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int n, d, a[mn], pre[mn], suf[mn], dp[mn];

int bit[mn << 1], ss;

void push(int val){
    ss = val;
}

void add(int u, int val){
    while(u <= ss){
        bit[u] = max(bit[u], val);
        u += (u & -u);
    }
}

int get(int u){
    int res = 0;
    while(u){
        res = max(res, bit[u]);
        u -= (u & -u);
    }
    return res;
}

void add1(int u, int val){
    while(u <= ss){
        bit[u] = min(bit[u], val);
        u += (u & -u);
    }
}

int get1(int u){
    int res = 0;
    while(u){
        res = min(res, bit[u]);
        u -= (u & -u);
    }
    return res;
}
// Nx: Trước khi đi đến a[i] thì luôn đi từ gần nhất nhỏ hơn nó và cách <= d

int par[mn], sz[mn], min_val[mn], min_pos[mn];

void init(){
    for(int i = 1; i <= n; i++){
        par[i] = i, sz[i] = 1, min_val[i] = i;
    }
}

int find(int u){
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

int get_val(int u){
    return min_val[find(u)];
}

void join(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u, min_val[u] = min(min_val[u], min_val[v]);
}

bool cmp(pii a, pii b){
    if(a.fi == b.fi) return a.se > b.se;
    return a.fi < b.fi;
}

int st[mn << 2];

void update(int id, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        st[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, pos, val);
    update(id << 1 | 1, mid + 1, r, pos, val);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(l >= u && r <= v) return st[id];
    int mid = (l + r) >> 1;
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}

void solve(){
    cin >> n >> d;
    vector <int> comp;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        comp.push_back(a[i]);
    }

    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    for(int i = 1; i <= n; i++) a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
    
    ss = comp.size();
    
    for(int i = 1; i <= n; i++){
        if(a[i] > 1) pre[i] = get(a[i] - 1);
        if(pre[i] == 0 || i - pre[i] > d) pre[i] = i;
        add(a[i], i);
    }

    fill(bit, bit + mn, inf);

    for(int i = n; i >= 1; i--){
        if(a[i] > 1) suf[i] = get1(a[i] - 1);
        if(suf[i] == inf || suf[i] - i > d) suf[i] = i;
        add1(a[i], i);
        // cout << suf[i] << ' ';
    }
    // cout << '\n';

    vector <pii> Megumi;
    for(int i = 1; i <= n; i++) Megumi.push_back({a[i], i});
    sort(all(Megumi), cmp);

    init();

    for(auto [val, pos] : Megumi){
        join(pos, pre[pos]);
        join(pos, suf[pos]);
        min_pos[pos] = get_val(pos);
    }
    int ans = 0;
    for(auto [val, pos] : Megumi){
        dp[pos] = get(1, 1, n, min_pos[pos], pos) + 1;
        update(1, 1, n, pos, dp[pos]);
        ans = max(ans, dp[pos]);
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35