Submission #3049924

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }
//

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}

int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    // assert(i <= N);
    return i;
}


void solve(int N, vi& a) {
    map<int,vi> st;
    rep(i,N) {
        st[a[i]].pb(1+i);
    }
    // cerr << st << endl;

    vector<ll> b(N+1, 0);

    // ai <= 1e9
    ll last_top=-1, last_w=0, last_ai=INT_MAX;
    for (auto it=st.rbegin(); it!=st.rend(); ++it) {
        int ai = it->first; // vi is = z.second;
        if (last_top >= 0) {
            b[last_top] = last_w * (last_ai - ai);
            // fprintf(stderr, "b[%d] = %d x (%d - %d) = %d\n",
            //     last_top, last_w, last_ai, ai, b[last_top]);
        }

        last_top = it->second[0];
        last_w += it->second.size();
        last_ai = ai;
    }

    b[last_top] = last_w * (last_ai - 0);

    rep1(i,N) {
        printf("%lld\n", b[i]);
    }
}

int main() {
    vi a;
    int N = loadvec(a);
    solve(N,a);
    return 0;
}

Submission Info

Submission Time
Task E - Frequency
User naoya_t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3280 Byte
Status
Exec Time 47 ms
Memory 13952 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt
All 0 / 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 896 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 5 ms 1152 KB
10.txt 1 ms 256 KB
11.txt 47 ms 9600 KB
12.txt 47 ms 9600 KB
13.txt 47 ms 9600 KB
14.txt 47 ms 9600 KB
15.txt 47 ms 9600 KB
16.txt 15 ms 3192 KB
17.txt 41 ms 13952 KB
18.txt 42 ms 13952 KB
19.txt 11 ms 2296 KB
20.txt 35 ms 6912 KB
21.txt 1 ms 256 KB
22.txt 1 ms 256 KB
23.txt 1 ms 256 KB
24.txt 3 ms 1024 KB
25.txt 1 ms 256 KB
26.txt 1 ms 384 KB
27.txt 1 ms 256 KB
28.txt 37 ms 13952 KB
29.txt 40 ms 13952 KB
30.txt 40 ms 13952 KB
31.txt 37 ms 13952 KB
32.txt 37 ms 13952 KB
33.txt 37 ms 13952 KB
34.txt 39 ms 13952 KB
35.txt 40 ms 13952 KB
36.txt 37 ms 13952 KB
37.txt 36 ms 13952 KB