Submission #2114457
Source Code Expand
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int INF = 1e9; const ll LINF = 1e18; /* <url:https://agc005.contest.atcoder.jp/tasks/agc005_b> 問題文============================================================ すぬけ君はある日友人から長さ N の順列 a1,a2,…,aN を貰いました。 Σ{l = 1..N}Σ{r = l..N} min(al,al+1,...,ar) を求めてください。 制約 1≦N≦200,000 (a1,a2,…,aN) は (1,2,…,N) を並び替えたものである ================================================================= 解説============================================================= ================================================================ */ int main(void) { cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; vector<ll> b(N+1,0); for(int i = 1; i <= N;i++){ ll a; cin >> a; b[a] = i; } set<ll> s; s.insert(0); s.insert(N+1); ll ans = 0; for(ll i = 1; i <= N; i++){ auto it = s.lower_bound(b[i]); ans += i * (*it - b[i]) * (b[i] - *(--it)); s.insert(b[i]); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | clavis1107 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1241 Byte |
Status | AC |
Exec Time | 113 ms |
Memory | 11264 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
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 | AC | 92 ms | 11264 KB |
corner1 | AC | 92 ms | 11264 KB |
corner2 | AC | 1 ms | 256 KB |
corner3 | AC | 73 ms | 11264 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 112 ms | 11264 KB |
maxrand1 | AC | 111 ms | 11264 KB |
maxrand2 | AC | 113 ms | 11264 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |