Submission #7397356


Source Code Expand

Copy
#include <bits/stdc++.h>
#define P pair<int,ll>
using namespace std;
typedef long long ll;
const int maxx=1e5+10;
struct S{
    int id; ll val;
    bool operator < (const S &a) const{
        return val<a.val;
    }
};
S a[maxx];
set<int> aset;
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].val);
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=n;i;i--){
        ll l1=0,l2=0,r1=0,r2=0;
        aset.insert(a[i].id);
        auto it = aset.find(a[i].id);
        auto ik=it;
        ik++;
        if(ik==aset.end()){
            r1=n-a[i].id+1;
        }else{
            r1=(*ik)-a[i].id;
            ik++;
            if(ik==aset.end()){
                ik--;
                r2=n-(*ik)+1;
            }else{
                r2=*ik;
                ik--;
                r2-=*ik;
            }
        }
        ik=it;
        if(ik==aset.begin()){
            l1=a[i].id;
        }else{
            ik--;
            l1=a[i].id-(*ik);
            if(ik==aset.begin()){
                l2=(*ik);
            }else{
                l2=(*ik);
                ik--;
                l2-=(*ik);
            }
        }
        ans+=(l1*r2+l2*r1)*a[i].val;
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task E - Second Sum
User LIULIUii
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1334 Byte
Status AC
Exec Time 63 ms
Memory 6528 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:17:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i].val);
                                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 22
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-small-01.txt, 01-small-02.txt, 01-small-03.txt, 01-small-04.txt, 01-small-05.txt, 02-large-01.txt, 02-large-02.txt, 02-large-03.txt, 02-large-04.txt, 02-large-05.txt, 03-max-01.txt, 03-max-02.txt, 04-min-01.txt, 05-sorted-01.txt, 05-sorted-02.txt, 06-almost-sorted-01.txt, 06-almost-sorted-02.txt, 06-almost-sorted-03.txt, 06-almost-sorted-04.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 256 KB
00-sample-02.txt AC 2 ms 384 KB
00-sample-03.txt AC 1 ms 256 KB
01-small-01.txt AC 1 ms 256 KB
01-small-02.txt AC 1 ms 256 KB
01-small-03.txt AC 1 ms 256 KB
01-small-04.txt AC 1 ms 256 KB
01-small-05.txt AC 1 ms 256 KB
02-large-01.txt AC 55 ms 5760 KB
02-large-02.txt AC 33 ms 3712 KB
02-large-03.txt AC 57 ms 6016 KB
02-large-04.txt AC 58 ms 6144 KB
02-large-05.txt AC 35 ms 3968 KB
03-max-01.txt AC 63 ms 6528 KB
03-max-02.txt AC 62 ms 6528 KB
04-min-01.txt AC 1 ms 256 KB
05-sorted-01.txt AC 49 ms 6272 KB
05-sorted-02.txt AC 49 ms 6400 KB
06-almost-sorted-01.txt AC 47 ms 6016 KB
06-almost-sorted-02.txt AC 46 ms 5888 KB
06-almost-sorted-03.txt AC 49 ms 6272 KB
06-almost-sorted-04.txt AC 46 ms 6016 KB