Submission #535867

#	Time	Username	Problem	Language	Result	Execution time	Memory
535867		ddy888	Financial Report (JOI21_financial)	C++17	5 / 100	428 ms	56824 KiB

Main

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

int N, D;
int dp[300010], cnt[300010], ans;
vector<int> A, old;

struct node {
    node *l, *r;
    int val, s, m, e, lazy, upd;
    node(int _s, int _e) {
        s = _s, e = _e;
        m = (s + e) / 2;
        val = 0; lazy = 0; upd = false;
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void pushdown() { 
        if (upd) {
            val = lazy;
            if (s != e) {
                l->lazy = lazy;
                r->lazy = lazy;
            }
            upd = false;
        }
    }
    void set(int qs, int qe, int v) {
        if (qs == s && qe == e) {lazy = v; upd = true;}
        else {
            if (qs > m) r->set(qs, qe, v);
            else if (qe <= m) l->set(qs, qe, v);
            else l->set(qs, m, v), r->set(m + 1, qe, v);
            l->pushdown(), r->pushdown();
            val = max(l->val, r->val);
        }
    }
    int get(int qs, int qe) {
        pushdown();
        if (qs <= s && qe >= e) return val;
        if (qs > m) return r->get(qs, qe);
        if (qe <= m) return l->get(qs, qe);
        return max(l->get(qs, m), r->get(m + 1, qe));
    }
} *seg;

vector<int> discretize(vector<int> V) {
    vector<int> dis = V;
    sort(dis.begin() + 1,dis.end());
    dis.resize(unique(dis.begin() + 1,dis.end())-dis.begin());
    for (int i = 0; i < (int)V.size(); i++) {
        V[i + 1] = lower_bound(dis.begin() + 1,dis.end(), V[i + 1])-dis.begin();
    }   
    return V;
}

signed main() {
    fast;
    cin >> N >> D;
    A.resize(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    old = A;
    A = discretize(A);
    seg = new node(1, N);
    
    dp[1] = 1;
    seg->set(A[1], A[1], 1);
    cnt[A[1]] = 1;
    int lx = 1;
    for (int i = 2; i <= N; ++i) {
        ++cnt[A[i]];
        while (lx < N && i - lx > D) {
            --cnt[A[lx]];
            if (cnt[A[lx]] == 0) seg->set(A[lx], A[lx], 0);
            ++lx;
        }
        if (A[i] > 1) dp[i] = seg->get(1, A[i] - 1) + 1;
        else dp[i] = 1;
        // debug(i);
        // for (int j = 1; j <= N; ++j) cout << seg->get(j, j) << ' ';
        // cout<<endl;
        if (dp[i] > seg->get(A[i], A[i])) seg->set(A[i], A[i], dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;

    return 0;
}

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