AtCoder Grand Contest 005

Submission #1357805

Source codeソースコード

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define boost() ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cout << fixed; cout << setprecision(15); srand(time(NULL))
#define ordered_set tree <pair <int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
#define endl '\n'
const int _n = 1e6 + 11;
const long long inf = (long long)1e18 + 1LL;
const long long mod = 1e9 + 7;
const long double eps = 1e-7;

int n, a[_n], st[_n * 4];

void build (int p, int l, int r) {
  if (l == r) st[p] = l;
  else {
    build (2 * p, l, (l + r) / 2);
    build (2 * p + 1, (l + r) / 2 + 1, r);
    st[p] = ((a[st[2 * p]] < a[st[2 * p + 1]]) ? (st[2 * p]) : (st[2 * p + 1]));
  }
}

int get (int p, int l, int r, int L, int R) {
  if (l > r || l > R || r < L) return -1;
  if (l >= L && r <= R) return st[p];
  int v1 = get (2 * p, l, (l + r) / 2, L, R);
  int v2 = get (2 * p + 1, (l + r) / 2 + 1, r, L, R);
  if (v1 == -1 || v2 == -1) return max(v1, v2);
  return ((a[v1] < a[v2]) ? (v1) : (v2));
}

int solve (int l, int r) {
  if (l > r) return 0;
  int v = get(1, 0, n - 1, l, r);
  return (v - l + 1) * (r - v + 1) * a[v] + solve (l, v - 1) + solve (v + 1, r);
}

signed main () {
  boost();
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  build (1, 0, n - 1);
  cout << solve (0, n - 1) << endl;
  return 0;
}

Submission

Task問題 B - Minimum Sum
User nameユーザ名 erdenebayr_d
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 1610 Byte
File nameファイル名
Exec time実行時間 86 ms
Memory usageメモリ使用量 19840 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2
All 400 / 400 corner0,corner1,corner2,corner3,example0,example1,example2,maxrand0,maxrand1,maxrand2,rand0,rand1,rand2

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
corner0 AC 54 ms 10496 KB
corner1 AC 60 ms 19840 KB
corner2 AC 2 ms 2304 KB
corner3 AC 86 ms 15232 KB
example0 AC 2 ms 2304 KB
example1 AC 2 ms 2304 KB
example2 AC 2 ms 2304 KB
maxrand0 AC 65 ms 10496 KB
maxrand1 AC 65 ms 10496 KB
maxrand2 AC 64 ms 10496 KB
rand0 AC 2 ms 2304 KB
rand1 AC 2 ms 2304 KB
rand2 AC 2 ms 2304 KB