oj.uz

Submission #529637

# Submission time Handle Problem Language Result Execution time Memory
529637 2022-02-23T09:40:04 Z c28dnv9q3 Financial Report (JOI21_financial) C++17
5 / 100
 640 ms 53188 KB 
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>

#define MAX_N 300000

int vals[MAX_N], num_vals;
int scores[MAX_N];

struct node {
    int left, right;
    struct node *parent, *lchild, *rchild;

    int max;
} npool[MAX_N*2], *next_node = npool;
struct node *nmap[MAX_N];

struct node *create_tree(int l, int r, struct node *p = NULL) {
    assert(0 <= l && l < r && r <= num_vals);

    assert(next_node < npool + MAX_N*2);
    struct node *n = next_node++;

    n->left = l;
    n->right = r;
    n->parent = p;
    if(l == r-1) {
        n->lchild = NULL;
        n->rchild = NULL;
        n->max = 0;
        nmap[l] = n;
    } else {
        int m = l + (r - l) / 2;
        n->lchild = create_tree(l, m, n);
        n->rchild = create_tree(m, r, n);
        n->max = 0;
    }

    return n;
}

int query_tree(struct node *node, int l, int r) {
    if(r <= node->left || node->right <= l) return 0;
    if(l <= node->left && node->right <= r) return node->max;
    return std::max(query_tree(node->lchild, l, r), query_tree(node->rchild, l, r));
}

void activate_node(struct node *n) {
    assert(n->left == n->right - 1);

    n->max = scores[n->left];
    for(n = n->parent; n != NULL; n = n->parent) {
        n->max = std::max(n->lchild->max, n->rchild->max);
    }
}

struct nodeb {
    int left, right;
    struct nodeb *lchild, *rchild;

    int lazy_add;
    int max_bctr, max_bctr_idx;
} npoolb[2*MAX_N], *next_nodeb = npoolb;

static inline void update_lazyb(struct nodeb *n) {
    n->max_bctr += n->lazy_add;
    if(n->lchild != NULL) n->lchild->lazy_add += n->lazy_add;
    if(n->rchild != NULL) n->rchild->lazy_add += n->lazy_add;
    n->lazy_add = 0;
}

struct nodeb *create_treeb(int l, int r) {
    assert(0 <= l && l < r && r <= num_vals);

    assert(next_nodeb < npoolb + MAX_N*2);
    struct nodeb *n = next_nodeb++;

    n->left = l;
    n->right = r;
    n->lazy_add = 0;
    if(l == r-1) {
        n->lchild = NULL;
        n->rchild = NULL;
        n->max_bctr = 0;
        n->max_bctr_idx = l;
    } else {
        int m = l + (r - l) / 2;
        n->lchild = create_treeb(l, m);
        n->rchild = create_treeb(m, r);
        n->max_bctr = 0;
        n->max_bctr_idx = r-1;
    }

    return n;
}

void activate_nodeb(struct nodeb *node, int l, int r) {
    update_lazyb(node);

    if(r <= node->left || node->right <= l) return;
    if(l <= node->left && node->right <= r) {
        node->lazy_add++;
        update_lazyb(node);
        return;
    }

    activate_nodeb(node->lchild, l, r);
    activate_nodeb(node->rchild, l, r);

    if(node->lchild->max_bctr >= node->rchild->max_bctr) {
        node->max_bctr = node->lchild->max_bctr;
        node->max_bctr_idx = node->lchild->max_bctr_idx;
    } else {
        node->max_bctr = node->lchild->max_bctr;
        node->max_bctr_idx = node->lchild->max_bctr_idx;
    }
}

struct t {
    int bctr, idx;
};

struct t query_treeb(struct nodeb *node, int s) {
    update_lazyb(node);

    if(node->right <= s) return {-1, -1};
    if(s <= node->left) return {node->max_bctr, node->max_bctr_idx};

    t l = query_treeb(node->lchild, s), r = query_treeb(node->rchild, s);

    if(l.bctr >= r.bctr) return l;
    else return r;
}

int main() {
    int D;
    assert(scanf("%d %d", &num_vals, &D) == 2);
    assert(1 <= num_vals && num_vals <= MAX_N);

    for(int i = 0; i < num_vals; i++) assert(scanf("%d", vals+i) == 1);

    std::vector<int> svidx(num_vals);
    std::iota(svidx.begin(), svidx.end(), 0);
    std::sort(svidx.begin(), svidx.end(), [](int i1, int i2) { 
        if(vals[i1] == vals[i2]) return i1 < i2;
        return vals[i1] > vals[i2]; 
    });

    struct node *tree = create_tree(0, num_vals);
    struct nodeb *treeb = create_treeb(0, num_vals);

    for(auto i : svidx) {
        t t = query_treeb(treeb, i);
        if(t.idx < 0) t.idx = i;

        scores[i] = 1 + query_tree(tree, i+1, t.idx+D+1);
        activate_node(nmap[i]);
        activate_nodeb(treeb, i-D, i+D+1);
    }

    printf("%d\n", *std::max_element(scores, scores+num_vals));
    return EXIT_SUCCESS;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 216 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 268 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 280 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 216 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 268 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 280 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 216 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 268 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 280 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 53044 KB Output is correct
2 Correct 355 ms 53056 KB Output is correct
3 Incorrect 640 ms 53188 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 197 ms 53024 KB Output is correct
2 Correct 465 ms 53100 KB Output is correct
3 Correct 589 ms 53104 KB Output is correct
4 Correct 557 ms 53060 KB Output is correct
5 Correct 448 ms 53180 KB Output is correct
6 Correct 565 ms 53108 KB Output is correct
7 Correct 203 ms 53000 KB Output is correct
8 Correct 192 ms 53064 KB Output is correct
9 Correct 209 ms 52672 KB Output is correct
10 Correct 307 ms 52952 KB Output is correct
11 Correct 536 ms 53108 KB Output is correct
12 Correct 329 ms 53108 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 216 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 268 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 280 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -