Submission #907862


Source Code Expand

#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
typedef long long int ll;
typedef complex<double> P;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
typedef vector<double> Vec;
typedef vector<int> vec;
typedef vector<Vec> MAT;
typedef vector<vec> mat;
lli MOD = 1000000007;
#define MAX 200005
#define inf MAX
struct segtree {
    int N, dat[2 * MAX];
    segtree() {}
    segtree(int n)
    {
        N = 1;
        while (N < n)
            N *= 2;
        for (int i = 0; i < 2 * N - 1; i++)
            dat[i] = inf;
    }
    // update k th element
    void update(int k, int a)
    {
        k += N - 1;  // leaf
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    // min [a, b)
    int query(int a, int b) { return query(a, b, 0, 0, N); }
    int query(int a, int b, int k, int l, int r)
    {
        if (r <= a or b <= l)
            return inf;
        if (a <= l and r <= b)
            return dat[k];
        int m = (l + r) / 2;
        return min(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
    }
};
segtree seg = segtree(MAX);

int main()
{
    lli N;
    lli a[200005];
    cin >> N;
    rep(i, N)
    {
        cin >> a[i];
        seg.update(i, a[i]);
    }
    lli ans = 0;
    for (int i = 0; i < N; i++)
        for (int j = i; j < N; j++) {
            ans += seg.query(i, j + 1);
        }
    cout << ans << endl;
}

Submission Info

Submission Time
Task B - Minimum Sum
User uenoku
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1988 Byte
Status RE
Exec Time 118 ms
Memory 1792 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
RE × 3
RE × 13
Set Name Test Cases
Sample example0, example1, example2
All corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 RE 114 ms 1792 KB
corner1 RE 114 ms 1792 KB
corner2 RE 114 ms 1792 KB
corner3 RE 114 ms 1792 KB
example0 RE 114 ms 1792 KB
example1 RE 113 ms 1792 KB
example2 RE 114 ms 1792 KB
maxrand0 RE 113 ms 1792 KB
maxrand1 RE 113 ms 1792 KB
maxrand2 RE 113 ms 1792 KB
rand0 RE 115 ms 1792 KB
rand1 RE 118 ms 1792 KB
rand2 RE 117 ms 1792 KB