This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#define int long long
using namespace std;
int t[300000];
int lewo[300000];
int prawo[300000];
pair<int,int> drzewo[4000000][2];
int pot=1;
int wynik[300000];
vector<pair<int,pair<int,int> > > zapp[300000];
vector<pair<int,int> > zmiana[300000];
void add(int x,int l,int r,int a,int b,int co,int gdzie)
{
if(b<l || a>r)
return;
//cout<<"jestem w "<<x<<"\n";
if(a<=l && r<=b)
{
drzewo[x][gdzie].second+=co;
return;
}
int mid=(l+r)/2;
add(x*2,l,mid,a,b,co,gdzie);
add(x*2+1,mid+1,r,a,b,co,gdzie);
drzewo[x][gdzie].first=drzewo[x*2][gdzie].first+drzewo[x*2][gdzie].second*(mid-l+1)+drzewo[x*2+1][gdzie].first+drzewo[x*2+1][gdzie].second*(r-mid);
}
int zap(int x,int l,int r,int a,int b,int gdzie)
{
if(a>r || b<l)
return 0;
if(a<=l && r<=b)
return drzewo[x][gdzie].first+drzewo[x][gdzie].second*(r-l+1);
int mid=(l+r)/2;
return zap(x*2,l,mid,a,b,gdzie)+zap(x*2+1,mid+1,r,a,b,gdzie)+drzewo[x][gdzie].second*(min(b,r)-max(a,l)+1);
}
void dodaj(int x,int l,int r)
{
//cout<<x<<": "<<l<<" "<<r<<"\n";
zmiana[0].push_back({x,t[x]});
zmiana[l].push_back({x,-t[x]});
zmiana[r].push_back({r+x,-t[x]});
zmiana[l+r].push_back({x+r,t[x]});
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
while(pot<=800000)
pot*=2;
pot--;
for(int i=1;i<=n;i++)
cin>>t[i];
vector<int> Q;
t[0]=1e18;
t[n+1]=1e18;
Q.push_back(0);
for(int i=1;i<=n;i++)
{
while(Q.size() && t[Q.back()]<=t[i])
Q.pop_back();
lewo[i]=Q.back();
Q.push_back(i);
}
Q.clear();
Q.push_back(n+1);
for(int i=n;i>=1;i--)
{
while(Q.size() && t[Q.back()]<t[i])
Q.pop_back();
prawo[i]=Q.back();
Q.push_back(i);
}
for(int i=1;i<=n;i++)
{
if(lewo[i]==0)
lewo[i]=n+1;
else lewo[i]=i-lewo[i];
prawo[i]-=i;
dodaj(i,lewo[i],prawo[i]);
}
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
zapp[x].push_back({i,{y,z}});
}
int stala=400000;
for(int i=0;i<=n;i++)
{
for(int j=0;j<zmiana[i].size();j++)
{
int gdzie=zmiana[i][j].first;
int ile=zmiana[i][j].second;
add(1,pot+1,pot*2+1,gdzie+pot,pot*2+1,ile,0);
add(1,pot+1,pot*2+1,stala+pot+1+gdzie,pot*2+1,-ile,1);
}
for(int j=0;j<zapp[i].size();j++)
{
int x=zapp[i][j].first;
int l=zapp[i][j].second.first;
int r=zapp[i][j].second.second;
wynik[x]=zap(1,pot+1,pot*2+1,l+pot,r+pot,0)+zap(1,pot+1,pot*2+1,stala+l+pot,stala+r+pot,1);
}
stala--;
}
for(int i=1;i<=m;i++)
cout<<wynik[i]<<"\n";
return 0;
}
Compilation message (stderr)
ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:94:22: 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]
94 | for(int j=0;j<zmiana[i].size();j++)
| ~^~~~~~~~~~~~~~~~~
ho_t5.cpp:101:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j=0;j<zapp[i].size();j++)
| ~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |