#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,i,ar[i]});
if(r&&l){
event[r-i].push_back({r-1,i,-ar[i]});
event[i-l].push_back({i-1,l,-ar[i]});
event[r-i+i-l].push_back({r-1,l,ar[i]});
return;
}
if(r){
event[r-i].push_back({r-1,i,-ar[i]});
return;
}
if(l){
event[i-l].push_back({i-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() {
init();
mnf.init(1000000);
mns.init(1000000);
mnf2.init(1000000);
mns2.init(1000000);
for(int t=0;t<=10;t++){
// cout<<t<<endl;
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);
mnf2.upd(a-1, (a-1)*c);
}
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);
cal+=mns.qsum(p-t)+(mnf.qsum(1000000)-mnf.qsum(p-t))*(p-t);
cal-=mns2.qsum(p)+(mnf2.qsum(1000000)-mnf2.qsum(p))*(p);
if(qry[t][i].second<0){
ans[id]-=cal;
}else{
ans[id]+=cal;
}
}
}
for(int i=1;i<=Q;i++){
cout<<ans[i]<<endl;
}
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:112:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<tri>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i=0;i<event[t].size();i++){
| ~^~~~~~~~~~~~~~~~
ho_t5.cpp:120: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]
120 | for(int i=0;i<qry[t].size();i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83084 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
83168 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83084 KB |
Output is correct |
| 2 |
Incorrect |
569 ms |
126692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83084 KB |
Output is correct |
| 2 |
Incorrect |
585 ms |
125820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
489 ms |
116436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
83084 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
83168 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
