Submission #529637

#	Time	Username	Problem	Language	Result	Execution time	Memory
529637		c28dnv9q3	Financial Report (JOI21_financial)	C++17	5 / 100	640 ms	53188 KiB

Main

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35