Submission #905401

---

Source Code Expand

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define all(a)  a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define mod 1000000007
#define _for(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

using namespace std;

int a[200005];
int N;
pair<int, int> dp1[200005][35];
pair<int, int> dp2[200005][35];

void pre(){
  for(int n = 0; n < N; ++n){
    dp1[n][0] = mp(a[n], n);
    dp2[n][0] = mp(a[n], n);
  }
  for(int j = 1; j <= 30; ++j){
    for(int i = 0; i <= (N - (1 << j)); ++i){
      if(dp1[i][j - 1].ff < dp1[i + (1 << (j - 1))][j - 1].ff){
        dp1[i][j] = dp1[i][j - 1];
      }
      else{
        dp1[i][j] = dp1[i + (1 << (j - 1))][j - 1];
      }

      if(dp2[i][j - 1].ff > dp2[i + (1 << (j - 1))][j - 1].ff){
        dp2[i][j] = dp2[i][j - 1];
      }
      else{
        dp2[i][j] = dp2[i + (1 << (j - 1))][j - 1];
      }
    }
  }
}

pair<int, int> queryMin(int l, int r){
  pair<int, int> res;
  res.ff = 1e9 + 7;
  res.ss = -1;
  int pl = l;
  int pr = r;
  for(int j = 30; j >= 0; --j){
    if(l + (1 << j) - 1 <= r){
      if(res.ff > dp1[l][j].ff){
        res = dp1[l][j];
      }
      l += (1 << j);
    }
  }
  assert(res.ss >= pl && res.ss <= pr);
  return res;
}

long long res = 0;

void solve(int l, int r){
   if(l > r) return;
   pair<int, int> idx = queryMin(l, r);
   long long right = (idx.ss - l + 1) * 1ll * (r - idx.ss + 1);
   res += idx.ff * right;
   solve(l, idx.ss - 1);
   solve(idx.ss + 1, r);
}

int main(){
   cin >> N;
   for(int n = 0; n < N; ++n){
      scanf("%d", &a[n]);
   }
   pre();
   solve(0, N - 1);
   cout << res << endl;
   return 0;
}

Submission Info

Compile Error

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

Judge Result