Kyselyt

input/code.cpp: In function 'void makeSumArr(std::vector<long long int>&)':
input/code.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); ++i) {
                  ~~^~~~~~~~~~

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N_MAX = 2e5+100;
ll sum_arr[N_MAX];
ll getSum(int a, int b) {
  return sum_arr[b+1] - sum_arr[a];
}
void makeSumArr(vector<ll>& v) {
  sum_arr[0] = 0;
  for(int i = 0; i < v.size(); ++i) {
    sum_arr[i+1] = sum_arr[i] + v[i];
  }
}
const int N = 1<<18;
int max_st[2*N];
int getMax(int a, int b) {
  a += N;
  b += N;
  int ma = 0;
  for(;a <= b; a/=2, b/=2) {
    if(a&1) {
      ma = max(ma, max_st[a++]);
    }
    if(~b&1) {
      ma = max(ma, max_st[b--]);
    }
  }
  return ma;
}
int n, q;
vector<ll> v;
int firstMoreThan(int pos, int val) {
  int lo = pos;
  int hi = n-1;
  int best = n;
  while(lo <= hi) {
    int mid = (lo+hi)/2;
    if(getMax(pos, mid) > val) {
      hi = mid-1;
      best = mid;
    }
    else {
      lo = mid+1;
    }
  }
  return best;
}
ll ans_from[N_MAX];
int main() {
  cin>>n>>q;
  v.resize(n+1);
  for(int i = 0; i < n; ++i) {
    cin>>v[i];
    max_st[N+i] = v[i];
  }
  v[n] = 2e9;
  makeSumArr(v);
  for(int i = N-1; i >= 0; --i) {
    max_st[i] = max(max_st[i*2], max_st[i*2+1]);
  }
  vector<pair<int, int> > faster;
  faster.push_back({v[n], n});
  for(int i = n-1; i >= 0; --i) {
    //ll first_more = firstMoreThan(i, v[i]);
    while(faster.back().first <= v[i]) {
      faster.pop_back();
    }
    ll first_more = faster.back().second;
    faster.push_back({v[i], i});
    //std::cout << first_more << ' ' << firstMoreThan(i, v[i]) << endl;
    ans_from[i] = ans_from[first_more];
    ll seg_length = first_more - i - 1;
    ans_from[i] += seg_length * v[i] - getSum(i+1, first_more-1);
  }
  for(int i = 0; i < q; ++i) {
    int a, b;
    cin>>a>>b;
    --a, --b;
    ll ans = ans_from[a];
    ll value_at_b = getMax(a, b);
    ll first_more_after_b = firstMoreThan(b, value_at_b);
    ans -= ans_from[first_more_after_b];
    ll seg_length = first_more_after_b - b - 1;
    ans -= seg_length * value_at_b - getSum(b+1, first_more_after_b-1);
    cout<<ans<<endl;
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED