oj.uz

Submission #811669

# Submission time Handle Problem Language Result Execution time Memory
811669 2023-08-07T05:19:27 Z vjudge1 Financial Report (JOI21_financial) C++17
5 / 100
 1712 ms 974060 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, k = 0;
    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] = get(m, root) + 1;
        mp[m].add(dp[i]);
        update(m, root);
        k = max(k, dp[i]);
    }
    cout << k;
}

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 1 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 220 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 0 ms 224 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 344 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 220 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 0 ms 224 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 344 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 220 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 0 ms 224 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 344 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 1452 KB Output is correct
2 Incorrect 166 ms 1504 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 116 ms 5184 KB Output is correct
2 Correct 157 ms 5616 KB Output is correct
3 Correct 370 ms 16656 KB Output is correct
4 Correct 1712 ms 955540 KB Output is correct
5 Correct 1236 ms 955420 KB Output is correct
6 Correct 1403 ms 954944 KB Output is correct
7 Correct 825 ms 973932 KB Output is correct
8 Correct 807 ms 974060 KB Output is correct
9 Correct 825 ms 949632 KB Output is correct
10 Correct 1024 ms 952348 KB Output is correct
11 Correct 1418 ms 955448 KB Output is correct
12 Correct 1284 ms 955396 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 220 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 0 ms 224 KB Output is correct
10 Correct 0 ms 216 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 344 KB Output isn't correct
16 Halted 0 ms 0 KB -