CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Kyselyt
Sender:kluopaja
Submission time:2020-10-18 20:49:59 +0300
Language:C++ (C++11)
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2--2, 3details
#3--3details
#4ACCEPTED0.85 s3details
#5--3details

Compiler report

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) {
                  ~~^~~~~~~~~~

Code

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N_MAX = 2e5+100;
ll sum_arr[N_MAX];
int 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-1;
  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]);
  }
  for(int i = n-1; i >= 0; --i) {
    ll first_more = firstMoreThan(i, v[i]);
    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 details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 100
70 8 72 88 42 78 85 41 23 36 6...

correct output
99
0
922
2579
1892
...

user output
99
0
922
2579
1892
...
Truncated

Test 2

Group: 2, 3

Verdict:

input
200000 200000
98 99 29 92 29 81 100 52 89 80...

correct output
1497732
2810356
9532632
6655773
5403513
...

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000 200000
818377786 934884634 816080381 ...

correct output
86877225712611
94684086875470
92703793485296
38149694892093
61948503092286
...

user output
(empty)

Test 4

Group: 3

Verdict: ACCEPTED

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...
Truncated

Test 5

Group: 3

Verdict:

input
200000 200000
200000 199999 199998 199997 19...

correct output
15920862903
3193483321
18874982071
4846348926
3970697055
...

user output
(empty)