Submission #1604987


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <fstream>
#include <bitset>
#include <time.h>
#include <assert.h>
#include <unordered_map>

#define LL long long
#define VI vector<int>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define bitcount(b) __builtin_popcount(b)
const double EPS = 1e-10;
const double PI = acos(-1.0);
#define MOD 1000000007

using namespace std;

class SegmentTree {
public:
    const int MAX_N = 1 << 17;
    int n;
    vector<int> dat;
    
    SegmentTree(int n_) {
        this->n = 1;
        while (this->n < n_) { this->n *= 2; }
        this->dat = vector<int>(2 * MAX_N - 1, INT_MAX);
    }

    // k番目の値(0-indexed)をaに変更
    void update(int k, int a) {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    // [a, b)の最小値を求める
    int query(int a, int b) {
        return query(a, b, 0, 0, this->n);
    }

    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return INT_MAX;
        }
        if (a <= l && r <= b) {
            return dat[k];
        }
        else {
            int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }

};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, a;
    cin >> N;
    SegmentTree st = SegmentTree(N);
    FOR(i, 0, N) {
        cin >> a;
        st.update(i, a);
    }

    LL ans = 0;
    FOR(l, 0, N) {
        FOR(r, l, N) {
            ans += st.query(l, r + 1);
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task B - Minimum Sum
User MitI_7
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2652 Byte
Status RE
Exec Time 246 ms
Memory 1280 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 7
RE × 6
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 246 ms 1280 KB
corner1 RE 97 ms 1280 KB
corner2 AC 3 ms 1280 KB
corner3 RE 97 ms 1280 KB
example0 AC 2 ms 1280 KB
example1 AC 2 ms 1280 KB
example2 AC 1 ms 1280 KB
maxrand0 RE 96 ms 1280 KB
maxrand1 RE 97 ms 1280 KB
maxrand2 RE 96 ms 1280 KB
rand0 AC 4 ms 1280 KB
rand1 AC 2 ms 1280 KB
rand2 AC 2 ms 1280 KB