oj.uz

Submission #811764

# Submission time Handle Problem Language Result Execution time Memory
811764 2023-08-07T05:44:50 Z vjudge1 Financial Report (JOI21_financial) C++17
5 / 100
 1465 ms 973936 KB 
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 300300;

int dp[N];

struct SlideWin{
    stack < int > L, R, S;

    void add(int x) {
        R.push(max(R.empty() ? 0 : R.top(), x));
        S.push(x);
    }

    void del() {
        if(L.empty()) {
            for(; !S.empty();) {
                L.push(max(L.empty() ? 0 : L.top(), S.top()));
                S.pop();
                R.pop();
            }
        }
        L.pop();
    }

    int get_max() {
        return max(L.empty() ? 0 : L.top(),
                   R.empty() ? 0 : R.top());
    }
};

map < int, SlideWin > mp;

struct node{
    int l, r, mx = 0;
    node *left = NULL, *right = NULL;

    node(int _l, int _r):l(_l), r(_r) {};
};

void check(node *x) {
    if(x->left == NULL) {
        x->left = new node(x->l, (x->l + x->r) / 2);
    }
    if(x->right == NULL) {
        x->right = new node((x->l + x->r) / 2, x->r);
    }
}

void update(int pos, node *x) {
    if(x->l + 1 == x->r) {
        x->mx = mp[x->l].get_max();
        return;
    }
    check(x);
    pos < x->left->r ?
    update(pos, x->left)  :
    update(pos, x->right) ;

    x->mx = max(x->left->mx, x->right->mx);
}

int get(int r, node *x) {
    if(x->r <= r || x->mx == 0) {
        return x->mx;
    }
    check(x);
    int res = get(r, x->left);
    if(x->right->l < r) {
        res = max(res, get(r, x->right));
    }
    return res;
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, d;
    cin >> n >> d;
    queue < int > q;
    node *root = new node(0, (1<<30));
    for(int i = 1; i <= n; ++ i) {
        cin >> m;
        if(q.size() > d) {
            mp[q.front()].del();
            update(q.front(), root);
            q.pop();
        }
        q.push(m);
        dp[i] = max(get(m, root) + 1, mp[m].get_max());
        mp[m].add(dp[i]);
        update(m, root);
    }
    int mx = 0;
    for(int i = n - d + 1; i <= n; ++ i) {
        mx = max(mx, dp[i]);
    }
    cout << mx;
}

Compilation message

Main.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:98:21: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |         if(q.size() > d) {
      |            ~~~~~~~~~^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 1456 KB Output is correct
2 Incorrect 162 ms 1452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 5128 KB Output is correct
2 Correct 177 ms 5520 KB Output is correct
3 Correct 383 ms 16688 KB Output is correct
4 Correct 1465 ms 955604 KB Output is correct
5 Correct 1223 ms 955476 KB Output is correct
6 Correct 1400 ms 954900 KB Output is correct
7 Correct 812 ms 973864 KB Output is correct
8 Correct 820 ms 973936 KB Output is correct
9 Correct 833 ms 949588 KB Output is correct
10 Correct 1151 ms 952320 KB Output is correct
11 Correct 1464 ms 955432 KB Output is correct
12 Correct 1374 ms 955372 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -