Submission #1687126
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl #define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<double> vd; typedef vector<P> vp; const int MAX_N = 200005; int pos[MAX_N]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n){ int a; cin >> a; --a; pos[a] = i; } set<int> st; ll ans = 0; rep(i,n){ auto it = st.lower_bound(pos[i]); ll l,r; if(it == st.end()){ if(it == st.begin()){ ans += (ll)(i+1)*(pos[i]+1)*(n-pos[i]); }else{ it--; l = *it; ans += (ll)(i+1)*(pos[i]-l)*(n-pos[i]); } }else if(it == st.begin()){ r = *it; ans += (ll)(i+1)*(pos[i]+1)*(r-pos[i]); }else{ r = *it; it--; l = *it; ans += (ll)(i+1)*(pos[i]-l)*(r-pos[i]); } st.insert(pos[i]); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | kopricky |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1969 Byte |
Status | AC |
Exec Time | 110 ms |
Memory | 10368 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 | 108 ms | 10368 KB |
corner1 | AC | 110 ms | 10368 KB |
corner2 | AC | 1 ms | 256 KB |
corner3 | AC | 68 ms | 10368 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 105 ms | 10368 KB |
maxrand1 | AC | 105 ms | 10368 KB |
maxrand2 | AC | 105 ms | 10368 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |