Submission #1116969


Source Code Expand

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

using namespace std;

const int MAX_N = 2e5 + 10;

long long n;
long long a[MAX_N];
set<pair<long long, int>> s;
long long ans[MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert({a[i], -i});
    }
    auto itr = s.end();
    itr--;
    int id = -itr->second;
    long long am = a[id];
    long long cnt = 1;
    while (1) {
        while (itr != s.begin() && itr->first == am) {
            itr--;
            cnt++;
        }
        if (itr->first != am) {
            cnt--;
            long long d = am - itr->first;
            ans[id] += d * cnt;
            id = min(id, -itr->second);
            am = itr->first;
            cnt++;
        } else {
            ans[id] += am * cnt;
            break;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << "\n";
    }
}

Submission Info

Submission Time
Task E - Frequency
User trilis
Language C++14 (GCC 5.4.1)
Score 700
Code Size 993 Byte
Status
Exec Time 54 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 4 ms 768 KB
03.txt 1 ms 256 KB
04.txt 1 ms 384 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 5 ms 896 KB
10.txt 1 ms 256 KB
11.txt 52 ms 7552 KB
12.txt 54 ms 7552 KB
13.txt 53 ms 7552 KB
14.txt 52 ms 7552 KB
15.txt 52 ms 7552 KB
16.txt 44 ms 7552 KB
17.txt 46 ms 8704 KB
18.txt 44 ms 7552 KB
19.txt 40 ms 7552 KB
20.txt 51 ms 7552 KB
21.txt 1 ms 256 KB
22.txt 1 ms 256 KB
23.txt 1 ms 256 KB
24.txt 3 ms 768 KB
25.txt 1 ms 256 KB
26.txt 1 ms 384 KB
27.txt 1 ms 256 KB
28.txt 39 ms 8832 KB
29.txt 41 ms 8832 KB
30.txt 42 ms 8960 KB
31.txt 40 ms 8832 KB
32.txt 41 ms 8832 KB
33.txt 38 ms 7552 KB
34.txt 38 ms 7552 KB
35.txt 39 ms 7552 KB
36.txt 37 ms 7552 KB
37.txt 37 ms 7552 KB