이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
struct node{
ll val=0,tag=0;
};
vector<ll> vec;
vector<node> seg;
void build(int l,int r,int ind){
if(l==r){
seg[ind].val=vec[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ind*2);
build(mid+1,r,ind*2+1);
seg[ind].val=seg[ind*2].val+seg[ind*2+1].val;
}
void push(int l,int r,int ind){
if(l==r) return;
int mid=(l+r)>>1;
seg[ind*2].val+=seg[ind].tag*(mid-l+1);
seg[ind*2+1].val+=seg[ind].tag*(r-mid);
seg[ind*2].tag+=seg[ind].tag;
seg[ind*2+1].tag+=seg[ind].tag;
seg[ind].tag=0;
}
void modify(int l,int r,int start,int end,ll num,int ind){
if(r<start||end<l) return;
if(start<=l&&r<=end){
seg[ind].val+=num*(r-l+1);
seg[ind].tag+=num;
return;
}
push(l,r,ind);
int mid=(l+r)>>1;
modify(l,mid,start,end,num,ind*2);
modify(mid+1,r,start,end,num,ind*2+1);
seg[ind].val=seg[ind*2].val+seg[ind*2+1].val;
}
ll query(int l,int r,int start,int end,int ind){
if(r<start||end<l) return 0;
if(start<=l&&r<=end) return seg[ind].val;
push(l,r,ind);
int mid=(l+r)>>1;
return query(l,mid,start,end,ind*2)+query(mid+1,r,start,end,ind*2+1);
}
struct rng{
int l,r;
ll lnum,rnum;
rng(int _l,int _r,ll _lnum,ll _rnum){
l=_l,r=_r,lnum=_lnum,rnum=_rnum;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
ll d;
cin>>n>>d;
seg.resize(4*n+4);
vec.resize(n+1);
vector<ll> pre(n+1);
for(int i=1;i<=n;i++) cin>>vec[i],pre[i]=pre[i-1]+vec[i];
build(1,n,1);
vector<vector<pair<int,int>>> events(n+1);
int q;
cin>>q;
vector<ll> ans(q);
int a,b;
for(int i=0;i<q;i++){
cin>>a>>b;
events[b].push_back(make_pair(a,i));
}
vector<rng> st;
for(int i=1;i<=n;i++){
int nowl=i,nowr=i;
ll nowlnum=vec[i],nowrnum=vec[i];
while(!st.empty()){
auto [l,r,lnum,rnum]=st.back();
//cout<<l<<" "<<r<<" "<<lnum<<" "<<rnum<<"\n";
if(rnum+d<=nowlnum) break;
st.pop_back();
ll res=(rnum-nowlnum-1)/d+1;
if(rnum<=nowlnum) res=0;
modify(1,n,l,r,-d*res,1);
nowl=l;
nowlnum=lnum-d*res;
}
st.emplace_back(nowl,nowr,nowlnum,nowrnum);
for(auto &[l,id]:events[i]){
if(query(1,n,l,l,1)<0) ans[id]=-1;
else ans[id]=((pre[i]-pre[l-1])-query(1,n,l,i,1))/d;
}
}
for(auto x:ans) cout<<x<<"\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... |