Submission #1354617

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define upmin(ans,ansx) (ans)=min((ans),(ansx))
#define upmax(ans,ansx) (ans)=max((ans),(ansx))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MOD (1000000009)
#define MAXN (200005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int SegTree[MAXN<<2];
int A[MAXN], ReD[MAXN];
int N;

inline void insertSeg(const int& idx, const int& S, const int& E, const int& X, const int& P) {
    if(E < S || E < X || X < S) return; upmin(SegTree[idx], P);
    if(S == E) return;
    const int mid = (S+E)>>1;
    if(X <= mid) insertSeg(idx<<1, S, mid, X, P);
    else insertSeg((idx<<1)+1, mid+1, E, X, P);
}
inline int getSeg(const int& idx, const int& S, const int& E, const int& P, const int& Q) {
    if(E < S || E < P || Q < S) return INF;
    if(S == P && E == Q) return SegTree[idx];
    const int mid = (S+E)>>1;
    return min(getSeg(idx<<1, S, mid, max(S, P), min(mid, Q)), getSeg((idx<<1)+1, mid+1, E, max(mid+1, P), min(E, Q)));
}
ll f(const int& S, const int& E) {
    if(S > E) return 0;
    if(S == E) return A[S];
    ll ret = 0;
    const int idx = ReD[getSeg(1, 1, N, S, E)];
    ret = f(S, idx-1) + f(idx+1, E);
    ret += (ll)(idx-S+1) * (E-idx+1) * A[idx];
    return ret;
}

int main() {
    fill(SegTree, SegTree+(MAXN<<2), INF);
    scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
    for(int i = 1; i <= N; i++) insertSeg(1, 1, N, i, A[i]);
    for(int i = 1; i <= N; i++) ReD[A[i]] = i;
    printf("%lld\n", f(1, N));
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:61:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
                    ^
./Main.cpp:61:68: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
                                                                    ^

Judge Result