Submission #1157099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157099		dosts	Financial Report (JOI21_financial)	C++20	100 / 100	382 ms	66232 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e18,N = 5e5+1,MOD =  1e9+7;

vi v;

int idx(int x) {
    return upper_bound(all(v),x)-v.begin();
}


struct ST {
    vi t;

    ST(int nn) {
        t.assign(4*nn+1,0);
    }

    int query(int node,int l,int r,int L,int R) {
        if (l> R  || r < L) return 0;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }

    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = v;
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = max(t[2*node],t[2*node+1]);
    }
};
void solve() {  
    int n,d;
    cin >> n >> d;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) v.push_back(a[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    for (int i=1;i<=n;i++) a[i] = idx(a[i]);
    deque<int> dq;
    vi buck[n+1];
    for (int i=1;i<=n;i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        while (!dq.empty() && dq.front() <= i-d) dq.pop_front();
        if (i >= d) buck[a[dq.front()]].push_back(i-d+1);
    }
    vi pos[n+1];
    for (int i=1;i<=n;i++) pos[a[i]].push_back(i);
    vi L(n+1);
    set<int> inappropriate;
    for (int i = n;i>=1;i--) {
        if (pos[i].empty()) continue;
        for (auto it : buck[i]) inappropriate.insert(it);
        for (int p : pos[i]) {
            auto it = inappropriate.lower_bound(p-d+1);
            if (it == inappropriate.begin()) L[p] = 1;
            else L[p] = *(prev(it))+1;
        }
    }
    ST st(n);
    vi dp(n+1);
    int ans = 0;
    for (int i = 1;i<=n;i++) {
        for (auto p : pos[i]) {
            dp[p] = st.query(1,1,n,L[p],p-1)+1;
            ans = max(ans,dp[p]);
        }
        for (auto p : pos[i]) {
            st.update(1,1,n,p,dp[p]);
        }
    }
    cout << ans << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) 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