#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int lowbit(int x){return x&-x;}
struct STBIT{
vector<int>bit;
int MXN;
void init(int x){
for(int i=0;i<=x+10;i++){
bit.push_back(0);
}
MXN=x;
}
void upd(int pl,int vl){
while(pl<=MXN){
bit[pl]+=vl;
pl+=lowbit(pl);
}
}
int qsum(int pl){
if(pl<=0){return 0;}
int ret=0;
while(pl){
ret+=bit[pl];
pl-=lowbit(pl);
}
return ret;
}
};
struct tri{
int a;int b;int c;
};
int ar[1000006];
int lar[1000006];
int rar[1000006];
vector<tri>event[1000006];
int ans[1000006];
vector<pair<int,int>>qry[1000006];
STBIT mnf;
STBIT mns;
STBIT mnf2;
STBIT mns2;
int n;int Q;
void parallelogram(int i,int l,int r){
event[0].push_back({i-1+1,i,ar[i]});
if(r&&l){
event[r-i].push_back({r-1+1,i,-ar[i]});
event[i-l].push_back({i-1+1,l,-ar[i]});
event[r-i+i-l].push_back({r-1+1,l,ar[i]});
return;
}
if(r){
event[r-i].push_back({r-1+1,i,-ar[i]});
return;
}
if(l){
event[i-l].push_back({i-1+1,l,-ar[i]});
return;
}
}
void init(){
cin>>n>>Q;
n+=2;
for(int i=3;i<=n;i++){
cin>>ar[i];
}
for(int i=1;i<=Q;i++){
int t;int l;int r;
cin>>t>>l>>r;
l+=2;r+=2;
qry[t].push_back({i,r});
qry[t].push_back({i,-(l-1)});
}
stack<int>stk;
for(int i=3;i<=n;i++){
while(stk.size()&&ar[stk.top()]<=ar[i]){stk.pop();}
if(stk.size()){
lar[i]=stk.top();
}
stk.push(i);
}
while(stk.size()){stk.pop();}
for(int i=n;i>=3;i--){
while(stk.size()&&ar[stk.top()]<=ar[i]){stk.pop();}
if(stk.size()){
rar[i]=stk.top();
}
stk.push(i);
}
for(int i=3;i<=n;i++){
parallelogram(i,lar[i],rar[i]);
}
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
init();
mnf.init(1000000);
mns.init(1000000);
mnf2.init(1000000);
mns2.init(1000000);
for(int t=0;t<=10;t++){
// cout<<t<<":\n";
for(int i=0;i<event[t].size();i++){
int c;int a;int b;
c=event[t][i].c;b=event[t][i].b;a=event[t][i].a;
mnf.upd(b,c);
mns.upd(b,b*c);
mnf2.upd(a-1,c);
mns2.upd(a-1, (a-1)*c);
// cout<<a<<" "<<b<<" "<<c<<endl;
}
for(int i=0;i<qry[t].size();i++){
int id=qry[t][i].first;
int p=qry[t][i].second;
p=abs(p);
int cal=t*mnf.qsum(1000000);
// cout<<p<<" "<<p-t<<" ";
// cout<<cal<<" ";
cal+=mns.qsum(p-t)+(mnf.qsum(1000000)-mnf.qsum(p-t))*(p-t);
// cout<<cal<<" ";
cal-=mns2.qsum(p)+(mnf2.qsum(1000000)-mnf2.qsum(p))*(p);
// cout<<cal<<" ";
if(qry[t][i].second<0){
ans[id]-=cal;
}else{
ans[id]+=cal;
}
//cout<<id<<" "<<ans[id]<<"\n";
}
// cout<<endl;
}
for(int i=1;i<=Q;i++){
cout<<ans[i]<<endl;
}
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:115:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0;i<event[t].size();i++){
| ~^~~~~~~~~~~~~~~~
ho_t5.cpp:125:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int i=0;i<qry[t].size();i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83120 KB |
Output is correct |
| 2 |
Incorrect |
52 ms |
83188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83120 KB |
Output is correct |
| 2 |
Incorrect |
491 ms |
121812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83120 KB |
Output is correct |
| 2 |
Incorrect |
491 ms |
120948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
113084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83120 KB |
Output is correct |
| 2 |
Incorrect |
52 ms |
83188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
