Submission #2380528
Source Code Expand
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x) (x).begin(),(x).end()
# define UNIQ(c) (isok).erase(unique(ALL((isok))),(isok).end())
# define LOWER(s) transform(ALL((maze)),(maze).begin(),TL<char>)
# define UPPER(s) transform(ALL((maze)),(maze).begin(),TU<char>)
# define FOR(i,a,b) for(LL i=(a);i<(b);i++)
# define RFOR(i,a,b) for(LL i=(a);i>=(b);i--)
# define REP(i,n) FOR(i,0,n)
# define INIT std::ios::sync_with_stdio(false);std::cin.tie(0)
int n;
int a[201010];
int b[201010];
LL ans = 0;
int main() {
cin >> n;
REP(i, n) {
cin >> a[i];
b[a[i]] = i;
}
set<int> st;
st.insert(-1), st.insert(n);
for (int i = 1; i <= n;i++) {
auto r = st.upper_bound(b[i]);
auto l = r;
l--;
//cout << *l << " " << *r << endl;
st.insert(b[i]);
ans += ((*r) - b[i])*(b[i]-(*l))*i;
//cout << ans << endl;
}
cout << ans << endl;
//system("pause");
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
M3_cp |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1986 Byte |
Status |
WA |
Exec Time |
151 ms |
Memory |
11136 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
WA |
131 ms |
11136 KB |
corner1 |
WA |
134 ms |
11136 KB |
corner2 |
AC |
1 ms |
256 KB |
corner3 |
WA |
113 ms |
11136 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
WA |
151 ms |
11136 KB |
maxrand1 |
WA |
151 ms |
11136 KB |
maxrand2 |
WA |
151 ms |
11136 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |