CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Kyselyt
Sender:Laakeri
Submission time:2020-10-17 17:02:02 +0300
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED34
#3ACCEPTED54
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.15 s2, 3details
#3ACCEPTED0.17 s3details
#4ACCEPTED0.28 s3details
#5ACCEPTED0.14 s3details

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;

ll a[202020];
ll st[202020];
int ne[202020][19];
ll st2[202020];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		st2[i]=st2[i-1]+a[i];
	}
	a[n+1]=1e9+10;
	for (int j=0;j<19;j++){
		ne[n+1][j]=n+1;
	}
	vector<pair<int, int>> x;
	x.push_back({n+1, a[n+1]});
	for (int i=n;i>=1;i--){
		while(x.back().S <= a[i]){
			x.pop_back();
		}
		assert(!x.empty());
		ne[i][0]=x.back().F;
		for (int j=1;j<19;j++){
			ne[i][j]=ne[ne[i][j-1]][j-1];
		}
		st[i]=a[i]*(ll)(ne[i][0]-i)+st[ne[i][0]];
		x.push_back({i, a[i]});
	}
	for (int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		ll ans=st[l];
		int d=l;
		for (int j=18;j>=0;j--){
			while (ne[d][j]<=r){
				d=ne[d][j];
			}
		}
		assert(d>=l&&a[d]>=a[l]&&d<=r);
		ans-=st[d];
		ans+=(ll)(r-d+1)*a[d];
		ans-=st2[r]-st2[l-1];
		cout<<ans<<'\n';
	}
}

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
...

Test 2

Group: 2, 3

Verdict: ACCEPTED

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

correct output
1497732
2810356
9532632
6655773
5403513
...

user output
1497732
2810356
9532632
6655773
5403513
...

Test 3

Group: 3

Verdict: ACCEPTED

input
200000 200000
818377786 934884634 816080381 ...

correct output
86877225712611
94684086875470
92703793485296
38149694892093
61948503092286
...

user output
86877225712611
94684086875470
92703793485296
38149694892093
61948503092286
...

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
...

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
...