Submission #1679991
Source Code Expand
#include <bits/stdc++.h> #define F first #define int long long #define S second #define pb push_back #define Init ios::sync_with_stdio(0); const int MX = 1000*1000+100,inf = 0x7FFFFFFF,mod=1e9+7; using namespace std; int n; int inp[MX]; stack<int>stk; struct inx{ int r, l; }pos[MX]; int32_t main(){ Init cin>>n; for(int i=0;i<n;i++){ cin>>inp[i]; } for(int i=0;i<n;i++){ while(!stk.empty() && inp[stk.top()]>=inp[i]){ stk.pop(); } if(stk.empty()){ pos[i].l = 0; }else{ pos[i].l = stk.top()+1; } stk.push(i); } while(!stk.empty()){ stk.pop(); } for(int i=n-1;i>=0;i--){ while(!stk.empty() && inp[stk.top()]>=inp[i]){ stk.pop(); } if(stk.empty()){ pos[i].r = n; }else{ pos[i].r = stk.top(); } stk.push(i); } int sum=0; for(int i=0;i<n;i++){ int dis[2] = {(i+1)-pos[i].l, pos[i].r-(i)}; sum+=((dis[0]*dis[1])*inp[i])%mod; //cout<<i<<' '<<pos[i].r<<' '<<pos[i].l<<' '<<abs(pos[i].r-pos[i].l)*inp[i]<<endl; sum%=mod; } cout<<sum<<endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | ali_m |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1266 Byte |
Status | WA |
Exec Time | 26 ms |
Memory | 10112 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 | 23 ms | 10112 KB |
corner1 | WA | 22 ms | 10112 KB |
corner2 | AC | 2 ms | 2304 KB |
corner3 | WA | 25 ms | 9244 KB |
example0 | AC | 2 ms | 2304 KB |
example1 | AC | 2 ms | 2304 KB |
example2 | AC | 2 ms | 2304 KB |
maxrand0 | WA | 26 ms | 8448 KB |
maxrand1 | WA | 26 ms | 8448 KB |
maxrand2 | WA | 26 ms | 8448 KB |
rand0 | AC | 2 ms | 2432 KB |
rand1 | AC | 2 ms | 2304 KB |
rand2 | AC | 2 ms | 2304 KB |