이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/*
Suffix add 1 or point increase by D
D=1: do as many suffix increases as possible with Cartesian tree
D>1: suffix pattern must be same mod D
Ignore the mod D part by shifting the values to implicitly include the mod D part
*/
struct segtree{
int size;
std::vector<std::pair<long long,int>> nodes;
segtree(int n){
size=n;
nodes.resize(2*n-1,{1e18,-1});
}
void init(std::vector<long long>& vec,int nl,int nr,int ni){
if(nl+1>=nr){
nodes[ni]={vec[nl],nl};
}else{
int nm=(nl+nr)/2;
init(vec,nl,nm,ni+1);
init(vec,nm,nr,ni+2*(nm-nl));
nodes[ni]=std::min(nodes[ni+1],nodes[ni+2*(nm-nl)]);
}
}
std::pair<long long,int> query(int l,int r,int nl,int nr,int ni){
if(r<=nl||l>=nr)return {1e18,-1};
if(l<=nl&&r>=nr)return nodes[ni];
int nm=(nl+nr)/2;
return std::min(query(l,r,nl,nm,ni+1),query(l,r,nm,nr,ni+2*(nm-nl)));
}
std::pair<long long,int> query(int l,int r){
return query(l,r,0,size,0);
}
};
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
long long n,d;
std::cin>>n>>d;
std::vector<long long> vals,shifts,newvals;
for(int i=0;i<n;i++){
long x;
std::cin>>x;
vals.push_back(x);
if(i)shifts.push_back(shifts.back()+((x-vals[i-1])%d+d)%d);
else shifts.push_back(x%d);
newvals.push_back(vals.back()-shifts.back());
}
segtree rmin(n);
rmin.init(newvals,0,n,0);
std::vector<long long> cdp(1,0);//can underflow but don't care
std::vector<int> cinds(1,0);
std::vector<long long> cpsums(1,0);//can underflow
for(int i=1;i<=n;i++){
while(cinds.back()!=0&&newvals[cinds.back()-1]>newvals[i-1])cinds.pop_back();
cdp.push_back(cdp[cinds.back()]+(i-cinds.back())*newvals[i-1]);
cinds.push_back(i);
}
for(int i=0;i<n;i++){
cpsums.push_back(cpsums.back()+newvals[i]);
}
int q;
std::cin>>q;
while(q--){
int a,b;
std::cin>>a>>b;
a--;
std::pair<long long,int> curmin=rmin.query(a,b);
if(curmin.first+shifts[a]<0)std::cout<<"-1\n";
else{
long long btype=cdp[b]-cdp[curmin.second+1]+curmin.first*(curmin.second+1-a);
long long atype=((cpsums[b]-cpsums[a])-btype)/d;
std::cout<<atype<<'\n';
}
}
}
# | 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... |