Task: | Kyselyt |
Sender: | Gomhog |
Submission time: | 2020-10-16 21:06:00 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 34 |
#3 | ACCEPTED | 54 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.20 s | 2, 3 | details |
#3 | ACCEPTED | 0.22 s | 3 | details |
#4 | ACCEPTED | 0.23 s | 3 | details |
#5 | ACCEPTED | 0.21 s | 3 | details |
Code
#include <bits/stdc++.h>typedef long long ll;typedef long double ld;#define F first#define S secondusing namespace std;const int N=1<<18;const ll INF=9999999999;ll sum[201010];ll lstr[2*N], laz[2*N], matr[2*N];ll ans[201010];pair<pair<int,int>,int> query[201010];ll aa[201010];ll getSum(int a, int b, int nod, int ast,int bst) {if (a>=bst || b<=ast) return 0;if (laz[nod]>0) {int le = min(b,bst)-max(a,ast);return le*laz[nod];}if (a<=ast && b>=bst) return lstr[nod];int midst=(ast+bst)/2;return getSum(a,b,2*nod,ast,midst)+getSum(a,b,2*nod+1,midst,bst);}ll getSum(int a, int b) {return getSum(a,b,1,0,N);}void setVal(int a, int b, ll val, int nod, int ast, int bst) {if (a>=bst || b<=ast) return;if (bst-ast==1) {lstr[nod]=val;return;}if (ast>=a && bst<=b) {laz[nod]=val;lstr[nod]=(bst-ast)*val;return;}int midst=(ast+bst)/2;setVal(a,b,val,2*nod,ast,midst);setVal(a,b,val,2*nod+1,midst,bst);laz[nod]=0;lstr[nod]=lstr[2*nod]+lstr[2*nod+1];}void setVal(int a, int b, ll val) {setVal(a,b,val,1,0,N);}int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n,q;cin>>n>>q;for (int i=0;i<n;i++) cin>>aa[i];aa[n]=INF;for (int i=0;i<n;i++) {sum[i+1]=aa[i]+sum[i];}for (int i=0;i<q;i++) {int a,b;cin>>a>>b;a--;b--;query[i]={{-a,b},i};}sort(query,query+q);vector<int> inIn;inIn.push_back(n);int cur=n;for (int i=0;i<q;i++) {int a=-query[i].F.F;int b=query[i].F.S;for (int j=cur-1;j>=a;j--) {while (aa[inIn.back()]<=aa[j]) inIn.pop_back();inIn.push_back(j);int hlp=inIn.size();setVal(inIn[hlp-1],inIn[hlp-2],aa[j]);}cur=a;ans[query[i].S]=getSum(a,b+1)-sum[b+1]+sum[a];}for (int i=0;i<q;i++) cout<<ans[i]<<"\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 ... Truncated |
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 ... Truncated |
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 ... Truncated |
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: ACCEPTED
input |
---|
200000 200000 200000 199999 199998 199997 19... |
correct output |
---|
15920862903 3193483321 18874982071 4846348926 3970697055 ... |
user output |
---|
15920862903 3193483321 18874982071 4846348926 3970697055 ... Truncated |