Submission #1695460
Source Code Expand
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x) cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif
//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
//ここから編集する
int main() {
int N;
cin >> N;
// vector<vector<bool> > flag(N, vector<bool>(N, false));
vector<int> a(N);
vector<int> pos(N + 1);
REP(i, 0, N) {
// cin >> a[i];
scanf("%d",&a[i]);
pos[a[i]] = i;
}
set<int> set1;
set<int> rset;
// set1.insert(-1);
set1.insert(N);
rset.insert(1);
ll ans = 0;
for (int i = 1; i <= N; i++) {
set1.insert(pos[i]);
rset.insert(-pos[i]);
auto itA = rset.upper_bound(-pos[i]);
auto itB = set1.upper_bound(pos[i]);
// printf("i = %d,*itA = %d,*itB = %d\n", i, -*itA, *itB);
ans += 1LL * i * (pos[i] + *itA) * (*itB - pos[i]);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time
2017-10-20 22:52:28+0900
Task
B - Minimum Sum
User
OMTWOCZWEIXVI
Language
C++14 (GCC 5.4.1)
Score
400
Code Size
2129 Byte
Status
AC
Exec Time
273 ms
Memory
20608 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:74:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
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
273 ms
20608 KB
corner1
AC
269 ms
20608 KB
corner2
AC
1 ms
256 KB
corner3
AC
131 ms
20608 KB
example0
AC
1 ms
256 KB
example1
AC
1 ms
256 KB
example2
AC
1 ms
256 KB
maxrand0
AC
194 ms
20608 KB
maxrand1
AC
198 ms
20608 KB
maxrand2
AC
243 ms
20608 KB
rand0
AC
1 ms
256 KB
rand1
AC
2 ms
256 KB
rand2
AC
1 ms
256 KB