oj.uz

Submission #535867

# Submission time Handle Problem Language Result Execution time Memory
535867 2022-03-11T15:03:34 Z ddy888 Financial Report (JOI21_financial) C++17
5 / 100
 428 ms 56824 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 54452 KB Output is correct
2 Correct 151 ms 54448 KB Output is correct
3 Incorrect 190 ms 54384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 54388 KB Output is correct
2 Correct 143 ms 54460 KB Output is correct
3 Correct 195 ms 54444 KB Output is correct
4 Correct 428 ms 56716 KB Output is correct
5 Correct 331 ms 56824 KB Output is correct
6 Correct 417 ms 56816 KB Output is correct
7 Correct 162 ms 56688 KB Output is correct
8 Correct 169 ms 56808 KB Output is correct
9 Correct 170 ms 56356 KB Output is correct
10 Correct 236 ms 56588 KB Output is correct
11 Correct 413 ms 56748 KB Output is correct
12 Correct 385 ms 56820 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -