CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Kyselyt
Sender:Sisuaski
Submission time:2020-10-17 07:27:38 +0300
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.22 s2, 3details
#30.27 s3details
#40.25 s3details
#5ACCEPTED0.28 s3details

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
typedef long long ll;
const int MN = 2<<17;
ll xs[MN];
ll bit[MN];
void add(int i, ll x) {
i+=2;
for(;i<MN;i+=i&-i) bit[i]+=x;
}
ll get(int i) {
i+=2;
ll r=0;
for(;i;i&=i-1) r+=bit[i];
return r;
}
struct Q {
int i, a, b;
bool operator<(const Q& q) const {
return b<q.b;
}
};
Q qs[MN];
struct S {
int i;
ll v;
};
ll sums[MN];
ll res[MN];
int main() {
int n,q;
cin>>n>>q;
for(int i=0; i<n; ++i) cin>>xs[i],sums[i+1]=sums[i]+xs[i];
for(int i=0; i<q; ++i) {
int a,b;
cin>>a>>b;
qs[i] = {i,a-1,b-1};
}
sort(qs,qs+q);
vector<S> st;
st.push_back({-1,1LL<<30});
for(int i=0,qi=0; i<n; ++i) {
ll x = xs[i];
int j=i;
while(x > st.back().v) {
S s = st.back();
st.pop_back();
add(s.i, s.v*(i-s.i));
add(j, -s.v*(i-s.i));
j = s.i;
}
if (st.empty() || x < st.back().v) {
st.push_back({i,x});
}
for(; qi<q && qs[qi].b == i; ++qi) {
int a=qs[qi].a, b=qs[qi].b;
auto it = partition_point(st.begin(), st.end(), [a](const S& s){return s.i < a;});
res[qs[qi].i] = get(a) + it->v * (b-it->i+1) - (sums[b+1]-sums[a]);
}
}
copy(res,res+q,ostream_iterator<ll>(cout,"\n"));
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

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
1776
-229
-468
...
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
-1536398
-2829664
-9680081
-6748797
-5494458
...
Truncated

Test 3

Group: 3

Verdict:

input
200000 200000
818377786 934884634 816080381 ...

correct output
86877225712611
94684086875470
92703793485296
38149694892093
61948503092286
...

user output
34902689251965
1094762554433
25988043795705
60692388948834
-34329706596377
...
Truncated

Test 4

Group: 3

Verdict:

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
-16716881610
-16588685493
-994380699
-16224678855
-4269676235
...
Truncated

Test 5

Group: 3

Verdict: ACCEPTED

input
200000 200000
200000 199999 199998 199997 19...

correct output
15920862903
3193483321
18874982071
4846348926
3970697055
...

user output
15920862903
3193483321
18874982071
4846348926
3970697055
...
Truncated