Submission #2857029
Source Code Expand
#include <limits.h> #include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define int long long #define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i) #define REV(i, a, b) for (int i = (a); i >= (b); --i) #define CLR(a, b) memset((a), (b), sizeof(a)) #define DUMP(x) cout << #x << " = " << (x) << endl; #define INF (LLONG_MAX - 1e5) #define fcout cout << fixed << setprecision(10) using namespace std; int N, A[300000]; signed main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; REP(i, N) { int a; cin >> a; A[a] = i; } set<int> s; s.insert(-1); s.insert(N); int ans = 0; FOR(i, 1, N) { int t = A[i]; auto itr = s.upper_bound(t); int high = *itr; int low = *(--itr); ans += i * (high - t) * (t-low); s.insert(t); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | tatsumack |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1467 Byte |
Status | AC |
Exec Time | 108 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 | 90 ms | 11264 KB |
corner1 | AC | 90 ms | 11264 KB |
corner2 | AC | 1 ms | 256 KB |
corner3 | AC | 70 ms | 11264 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 108 ms | 11264 KB |
maxrand1 | AC | 108 ms | 11264 KB |
maxrand2 | AC | 108 ms | 11264 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |