Submission #1304837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304837		BilAktauAlmansur	Financial Report (JOI21_financial)	C++20	100 / 100	662 ms	62780 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N = 3e5 + 7, M = 5e6 + 7, mod = 1e9 + 7;

int n, d, a[N], dp[N], last[N], lim[N][2];
vector<int> g[N];
int tr[4 * N];
void build(int x, int v, int lx, int rx) {
    tr[v] = x;
    if(lx == rx)return;
    int m = (lx + rx) >> 1;
    build(x, v + v, lx, m);
    build(x, v + v + 1, m + 1, rx);
}
void upd_mx(int i, int x, int v, int lx, int rx) {
    if(lx == rx) {
        tr[v] = max(tr[v], x);
        return;
    }
    int m = (lx + rx) >> 1;
    if(i <= m)upd_mx(i, x, v + v, lx, m);
    else upd_mx(i, x, v + v + 1, m + 1, rx);
    tr[v] = max(tr[v + v], tr[v + v + 1]);
}
int get_mx(int l, int r, int v, int lx, int rx) {
    if(lx > r || l > rx)return -1e9;
    if(lx >= l && r >= rx)return tr[v];
    int m = (lx + rx) >> 1;
    return max(get_mx(l, r, v + v, lx, m), get_mx(l, r, v + v + 1, m + 1, rx));
}
void upd_mn(int i, int x, int v, int lx, int rx) {
    if(lx == rx) {
        tr[v] = min(tr[v], x);
        return;
    }
    int m = (lx + rx) >> 1;
    if(i <= m)upd_mn(i, x, v + v, lx, m);
    else upd_mn(i, x, v + v + 1, m + 1, rx);
    tr[v] = min(tr[v + v], tr[v + v + 1]);
}
int get_mn(int l, int r, int v, int lx, int rx) {
    if(lx > r || l > rx)return 1e9;
    if(lx >= l && r >= rx)return tr[v];
    int m = (lx + rx) >> 1;
    return min(get_mn(l, r, v + v, lx, m), get_mn(l, r, v + v + 1, m + 1, rx));
}
int p[N], sz[N], mn[N], pref[N];
int get(int v) {
    if(p[v] == v)return v;
    else return p[v] = get(p[v]);
}
void unite(int x, int y) {
    x = get(x), y = get(y);
    if(sz[x] < sz[y])swap(x, y);
    if(x == y)return;
    sz[x] += sz[y];
    p[y] = x;
    mn[x] = min(mn[x], mn[y]);
}
void solve() {
    cin>>n>>d;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    // if(d == 1) {
    //     int mx = 0;
    //     stack<int> st;
    //     for(int i = n; i >= 1; i--) {
    //         while(st.size() && a[st.top()] <= a[i])st.pop();
    //         if(!st.size())dp[i] = 1;
    //         else dp[i] = dp[st.top()] + 1;
    //         st.push(i);
    //         mx = max(mx, dp[i]);
    //     }
    //     cout << mx << '\n';
    //     return;
    // }
    vector<int> vec;
    for(int i = 1; i <= n; i++) {
        vec.push_back(a[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    map<int, int> mp;
    int cur = 0;
    for(auto i : vec)mp[i] = ++cur;
    for(int i = 1; i <= n; i++) {
        a[i] = mp[a[i]];
        p[i] = i, sz[i] = 1, mn[i] = i;
        g[a[i]].push_back(i);
    }
    build(-1e9, 1, 1, n);
    for(int i = 1; i <= n; i++) {
        int x = get_mx(1, a[i], 1, 1, n);
        if(x == -1e9 || i - x > d)lim[i][0] = i;
        else lim[i][0] = x;
        upd_mx(a[i], i, 1, 1, n);
    }
    build(1e9, 1, 1, n);
    for(int i = n; i >= 1; i--) {
        int x = get_mn(1, a[i], 1, 1, n);
        if(x == 1e9 || x - i > d)lim[i][1] = i;
        else lim[i][1] = x;
        upd_mn(a[i], i, 1, 1, n);
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << lim[i][0] << ' ';
    // }cout << '\n';
    // for(int i = 1; i <= n; i++) {
    //     cout << lim[i][1] << ' ';
    // }cout << '\n';
    for(int i = 1; i <= n; i++) {
        reverse(g[i].begin(), g[i].end());
        for(auto j : g[i]) {
            unite(lim[j][0], j);
            unite(lim[j][1], j);
            pref[j] = mn[get(j)];
        }
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << i << ' ' << pref[i] << '\n';
    // }
    build(0, 1, 1, n);
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(auto j : g[i]) {
            int x = get_mx(pref[j], j, 1, 1, n) + 1;
            // cout << j << ' ' << x << '\n';
            ans = max(ans, x);
            upd_mx(j, x, 1, 1, n);
        }
    }
    cout << ans << '\n';
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T = 1;
    // cin>>T;
    while(T --)solve();
}

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