#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct node{
ll sum,dsum;
int cnt,dcnt;
int t;
pair<ll,int> get_val(int ct){
return {sum+dsum*(ct-t),cnt+dcnt*(ct-t)};
}
void update(ll vs,int vc,int ct){
auto tmp=get_val(ct);
sum=tmp.first;
dsum+=vs;
cnt=tmp.second;
dcnt+=vc;
t=ct;
}
};
node operator+(const node &a,const node &b){
node ret;
ret.sum=a.sum+b.sum;
ret.dsum=a.dsum+b.dsum;
ret.cnt=a.cnt+b.cnt;
ret.dcnt=a.dcnt+b.dcnt;
ret.t=max(a.t,b.t);
return ret;
}
const int MAX=(int)1e9+1;
int N,Q;
int A[200002];
int D1[200001],D2[200001];
node Tree[1<<19];
node init(int l,int r,int n){
if (l==r)
return Tree[n]={A[l],A[l],1,1,0};
int m=(l+r)>>1;
return Tree[n]=init(l,m,n<<1)+init(m+1,r,n<<1|1);
}
void update(int x,int v,int ct,int l,int r,int n){
Tree[n].update(A[x]*v,v,ct);
if (l==r)
return;
int m=(l+r)>>1;
if (x>m)
update(x,v,ct,m+1,r,n<<1|1);
else
update(x,v,ct,l,m,n<<1);
}
pair<ll,int> query(int lx,int rx,int ct,int l,int r,int n){
if (r<lx||rx<l)
return {0,0};
if (lx<=l&&r<=rx)
return Tree[n].get_val(ct);
int m=(l+r)>>1;
auto ret1=query(lx,rx,ct,l,m,n<<1);
auto ret2=query(lx,rx,ct,m+1,r,n<<1|1);
return {ret1.first+ret2.first,ret1.second+ret2.second};
}
ll my_query(int x,int ct){
if (!x)
return 0;
int l=1,r=N,k;
pair<ll,int> ret;
while (l<=r){
int m=(l+r)>>1;
auto tmp=query(1,m,ct,1,N,1);
if (tmp.second>=x){
k=m;
ret=tmp;
r=m-1;
}
else
l=m+1;
}
return ret.first-(ll)A[k]*(ret.second-x);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>Q;
for (int i=1; i<=N; i++)
cin>>A[i];
A[N+1]=MAX;
stack<int> s;
for (int i=1; i<=N; i++){
while (!s.empty()&&A[s.top()]<A[i])
s.pop();
if (!s.empty())
D1[i]=s.top();
s.push(i);
}
while (!s.empty())
s.pop();
s.push(N+1);
for (int i=N; i; i--){
while (A[s.top()]<=A[i])
s.pop();
D2[i]=s.top();
s.push(i);
}
vector<pair<int,pair<int,int>>> vu;
for (int i=1; i<=N; i++){
if (D1[i]){
int t1=i-D1[i]-1,t2=D2[i]-i-1;
vu.push_back({t1,{i,-1}});
vu.push_back({t2,{i,-1}});
vu.push_back({t1+t2+1,{i,1}});
}
else{
int t=D2[i]-i-1;
vu.push_back({t,{i,-1}});
}
}
sort(all(vu));
vector<pair<int,pair<pair<int,int>,int>>> vq;
for (int i=0,t,l,r; i<Q; i++){
cin>>t>>l>>r;
vq.push_back({t,{{l,r},i}});
}
sort(all(vq));
init(1,N,1);
vector<int> ans(Q);
for (int t=0,ui=0,qi=0; t<=N; t++){
for (; qi<(int)vq.size()&&vq[qi].first==t; qi++)
ans[vq[qi].second.second]=my_query(vq[qi].second.first.second,t)-my_query(vq[qi].second.first.first-1,t);
for (; ui<(int)vu.size()&&vu[ui].first==t; ui++)
update(vu[ui].second.first,vu[ui].second.second,t,1,N,1);
}
for (int i=0; i<Q; i++)
cout<<ans[i]<<"\n";
return 0;
}
Compilation message
ho_t5.cpp: In function 'll my_query(int, int)':
ho_t5.cpp:77:29: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | return ret.first-(ll)A[k]*(ret.second-x);
| ~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
1016 ms |
40812 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
1034 ms |
40740 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1079 ms |
37132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
