Submission #905100
Source Code Expand
#include<bits/stdc++.h> #define REP(i, n) for(int i=1; i<=n; i++) using namespace std; typedef long long ll; const int MAX = 1100100; int N; ll A[MAX], P[MAX], sol; set<ll> S; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; REP(I, N){ cin >> A[I]; P[A[I]] = I; } S.insert(0); S.insert(N+1); REP(I, N){ set<ll>::iterator it2 = S.upper_bound(P[I]); set<ll>::iterator it1 = it2; it1--; ll lo = *it1; ll hi = *it2; ll lft = P[I] - lo; ll rgt = hi - P[I]; sol += I*lft*rgt; S.insert(P[I]); } cout << sol << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | SandorGarcia |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 614 Byte |
Status | AC |
Exec Time | 150 ms |
Memory | 12800 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 | 118 ms | 12800 KB |
corner1 | AC | 118 ms | 12800 KB |
corner2 | AC | 3 ms | 256 KB |
corner3 | AC | 89 ms | 12800 KB |
example0 | AC | 3 ms | 256 KB |
example1 | AC | 3 ms | 256 KB |
example2 | AC | 3 ms | 256 KB |
maxrand0 | AC | 148 ms | 12800 KB |
maxrand1 | AC | 150 ms | 12800 KB |
maxrand2 | AC | 126 ms | 12800 KB |
rand0 | AC | 3 ms | 256 KB |
rand1 | AC | 3 ms | 256 KB |
rand2 | AC | 3 ms | 256 KB |