Submission #2822310

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 read_cr() {
    fgets(_buf, 256, stdin);
}


ll naive(int N, vi& a) {
    ll ans = 0LL;
    for (int l=0; l<N; ++l) {
        for (int r=l; r<N; ++r) {
            int minv = INT_MAX;
            for (int i=l; i<=r; ++i) {
                minv = min(minv, a[i]);
            }
            ans += minv;
        }
    }
    return ans;
}


inline ll f(int n) {
    // nC2
    return (ll)n*(n+1)/2;
}

ll fast(int N, vi& a) {
    ll ans = 0LL;
    // 区間数は1+2+..+N =N(N+1)/2
    // 1から順に、その数がminになるのが何回あるか数える?
    // 1有り範囲: [0 .. N) =
    // 1なし2有り範囲:  [) 1の位置 [)
    // 区間長n -> f(n)=n(n+1)/2
    // kで長さaの区間がa1,a2に分割されたとき(a=a1+a2+1)
    // kを含んでいた頃:f(a) これはminがk+1以上を含む
    // kを含まない頃 (minがk+1): f(a1)+f(a2)
    // 1つの数字の出現で高々1回しかsplitは発生しない
    // ... 20万回分割していくと?
    // 後でNから逆に包含を溶いていく?
    vector<ii> b(N);
    rep(i,N) b[i] = ii(a[i], i);
    sort(ALL(b)); // (1,w)...(N,w)
    vi aR(N+1);
    rep(i,N) aR[1+i] = b[i].second;
    aR[0] = -1;//
#ifdef DEBUG
    cerr << "aR: " << aR << endl;
#endif
    vector<ll> pat(N+1);
    pat[0] = f(N);

    set<ii> spans;
    spans.insert(ii(0,N)); // (from, len)
#ifdef DEBUG
    cerr << 0 << spans << endl;
#endif

    for (int x=1; x<=N; ++x) { // 200000
        int at = aR[x];
#ifdef DEBUG
        fprintf(stderr, "x=%d, at=%d", x, at); cerr << spans << endl;
#endif
        // if (spans.empty()) {
        //     break;
        // }

        auto it = spans.lower_bound(ii(at,N+1));
        assert(it != spans.begin());
        --it;

        int from = it->first, len = it->second;
        spans.erase(it);
        pat[x] = f(len);
        // [from, at), at, [at+1, from+len)
        if (from != at) {
            int sub_len = at - from;
            spans.insert(ii(from, sub_len));
            pat[x] -= f(sub_len);
        }
        if (at != from+len-1) {
            int sub_len = (from+len) - (at+1);
            spans.insert(ii(at+1, sub_len));
            pat[x] -= f(sub_len);
        }
        ans += (ll)x * pat[x];
#ifdef DEBUG
        cerr << x << spans << endl;
#endif
    }

    // ll patR(N+1, 0);
    // patR[n] = pat[n];
    // for (int i=N-1; i>=0; --i) {
    //     patR[i] = patR[i+1]
    // }

#ifdef DEBUG
    cerr << "pat:" << pat << endl;
#endif
    return ans;
}

ll solve(int N, vi& a) {
    ll ans = fast(N,a);
    // if (N < 100) {
    //     ll naive_ans = naive(N,a);
    //     assert(ans == naive_ans);
    // }
    return ans;
}

int main() {
    vi a;
    int N = loadvec(a);
    cout << solve(N,a) << endl;
    // cout << (solve(N,a) ? "Yes":"No") << endl;
    return 0;
}

Submission Info

Submission Time
Task B - Minimum Sum
User naoya_t
Language C++14 (GCC 5.4.1)
Score 400
Code Size 5356 Byte
Status
Exec Time 103 ms
Memory 8576 KB

Compile Error

./Main.cpp: In function ‘void read_cr()’:
./Main.cpp:87:28: warning: ignoring return value of ‘char* fgets(char*, int, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
     fgets(_buf, 256, stdin);
                            ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2
All 400 / 400 corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 25 ms 6144 KB
corner1 24 ms 6144 KB
corner2 1 ms 256 KB
corner3 39 ms 6144 KB
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
maxrand0 103 ms 8576 KB
maxrand1 103 ms 8576 KB
maxrand2 103 ms 8576 KB
rand0 1 ms 256 KB
rand1 1 ms 256 KB
rand2 1 ms 256 KB