Submission #1118277


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

struct tree
{
    int x, y;
    int size;
    long long sum = 0;
    tree *l, *r;

    tree(int _x) {
        x = _x;
        y = rand();
        l = r = 0;
        size = 1;
        sum = x;
    }
};

typedef tree *ptree;

inline int si(ptree r)
{
    return r ? r->size : 0;
}

inline long long sum(ptree r) {
    return r ? r->sum : 0ll;
}

inline void update(ptree r)
{
    if (!r) {
        return;
    }
    r->size = si(r->l) + si(r->r) + 1;
    r->sum = sum(r->l) + sum(r->r) + r->x;
}

ptree merge(ptree l, ptree r)
{
    if (!l) {
        return r;
    }
    if (!r) {
        return l;
    }
    if (l->y > r->y) {
        l->r = merge(l->r, r);
        update(l);
        return l;
    } else {
        r->l = merge(l, r->l);
        update(r);
        return r;
    }
}

void split(ptree root, ptree &l, ptree &r, int key)
{
    if (!root) {
        return (void)(l = r = 0);
    }

    if (root->x > key) {
        split(root->l, l, root->l, key);
        r = root;
    } else {
        split(root->r, root->r, r, key);
        l = root;
    }
    update(l);
    update(r);
}

inline void add_to_tree(ptree &root, int x)
{
    ptree l, r;
    split(root, l, r, x);
    root = merge(l, merge(new tree(x), r));
}


int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n;

    vector<long long> a;
    cin >> n;
    a.resize(n);
    vector<long long> result(n, 0);

    vector<long long> b_l, b_r;
    vector<bool> check_p;

    int cur_max = 0;
    int prev_max = 0;
    b_l.resize(n);
    b_r.resize(n);
    check_p.assign(n, false);
    for (int i = 0; i < a.size(); i++) {
        cin >> a[i];
        if (a[i] > cur_max) {
            prev_max = cur_max;
            cur_max = a[i];
            check_p[i] = true;
        }
        b_l[i] = prev_max;
        b_r[i] = cur_max;
    }

    ptree root = 0;
    for (int i = n - 1; i >= 0; i--) {
        add_to_tree(root, a[i]);

        if (check_p[i]) {
            ptree l1, r1, l2, r2;
            split(root, l1, r1, b_l[i]);
            split(r1, l2, r2, b_r[i]);

            result[i] += sum(l2) - b_l[i] * si(l2);
            result[i] += (b_r[i] - b_l[i]) * si(r2);

            root = merge(l1, merge(l2, r2));
        }
    }

    for (int i = 0; i < n; i++) {
        cout << result[i] << '\n';
    }
}

Submission Info

Submission Time
Task E - Frequency
User Dener
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2485 Byte
Status
Exec Time 94 ms
Memory 8960 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt
All 700 / 700 00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt
Case Name Status Exec Time Memory
00_example_01.txt 1 ms 256 KB
00_example_02.txt 1 ms 256 KB
01.txt 1 ms 256 KB
02.txt 5 ms 768 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 1 ms 256 KB
09.txt 6 ms 1024 KB
10.txt 1 ms 256 KB
11.txt 94 ms 8320 KB
12.txt 92 ms 8320 KB
13.txt 89 ms 8320 KB
14.txt 92 ms 8320 KB
15.txt 90 ms 8320 KB
16.txt 38 ms 8320 KB
17.txt 64 ms 8704 KB
18.txt 37 ms 8320 KB
19.txt 33 ms 8320 KB
20.txt 85 ms 8320 KB
21.txt 1 ms 256 KB
22.txt 1 ms 256 KB
23.txt 1 ms 256 KB
24.txt 5 ms 768 KB
25.txt 1 ms 256 KB
26.txt 1 ms 256 KB
27.txt 1 ms 256 KB
28.txt 67 ms 8832 KB
29.txt 63 ms 8960 KB
30.txt 64 ms 8960 KB
31.txt 64 ms 8960 KB
32.txt 63 ms 8832 KB
33.txt 39 ms 8320 KB
34.txt 38 ms 8320 KB
35.txt 37 ms 8320 KB
36.txt 39 ms 8320 KB
37.txt 39 ms 8320 KB