Submission #1222307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222307		noyancanturk	Fish 3 (JOI24_fish3)	C++20	100 / 100	358 ms	35164 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back

using pii=pair<int,int>;

const int lim=3e5+100;

struct fenw{
  int tree[lim];
  void update(int p,int val){
    p+=5;
    while(p<lim){
      tree[p]+=val;
      p+=p&-p;
    }
  }
  int query(int p){
    p+=5;
    int ans=0;
    while(p){
      ans+=tree[p];
      p-=p&-p;
    }
    return ans;
  }
  int query(int l,int r){
    return query(r)-query(l-1);
  }
};

struct{
  fenw con,speed;
  void update(int p,int val){
    if(p<0)return;
    speed.update(0,val);
    speed.update(p+1,-val);
    con.update(p+1,val*(p+1));
  }
  void update(int l,int r,int val){
    update(l-1,-val);
    update(r,val);
  }
  int query(int p){
    return con.query(p)+speed.query(p)*(p+1);
  }
  int query(int l,int r){
    return query(r)-query(l-1);
  }
}fw;

int n,d,q;
int a[lim],b[lim];
int l[lim],r[lim],ans[lim];
vector<int>g[lim];

int sub(int i,int j){
  i%=d;
  j%=d;
  if(j<=i)return i-j;
  return i-j+d;
}

signed main(){
  cin>>n>>d;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>l[i]>>r[i];
    g[r[i]].pb(i);
  }
  int L=1,curval=0;
  deque<int>st;
  for(int i=1;i<=n;i++){
    curval+=sub(a[i],a[i-1]);
    while(a[i]<curval){
      if(a[L]%d>a[L+1]%d){
        fw.update(L,i-1,1);
        curval-=d;
      }
      L++;
    }
    while(st.size()&&st.front()<L)st.pop_front();
    b[i]=(a[i]-curval)/d;
    fw.con.update(i,b[i]);
    while(st.size()&&b[i]<=b[st.back()]){
      int r=st.back();
      st.pop_back();
      int l=L;
      if(st.size())l=st.back()+1;
      fw.update(l,r,b[r]);
    }
    int ll=L;
    if(st.size())ll=st.back()+1;
    // for(int j=1;j<=i;j++){
    //   cerr<<fw.query(j,j)<<' ';
    // }cerr<<'\n';
    // cerr<<ll<<" huh\n";
    fw.update(ll,i,-b[i]);
    // for(int j=1;j<=i;j++){
    //   cerr<<fw.query(j,j)<<' ';
    // }cerr<<'\n';
    st.push_back(i);
    for(int j:g[i]){
      if(l[j]<L){
        ans[j]=-1;
      }else{
        ans[j]=fw.query(l[j],r[j]);
      }
    }
  }
  for(int i=0;i<q;i++){
    cout<<ans[i]<<'\n';
  }
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36