Submission #1065944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065944		NemanjaSo2005	Fish 3 (JOI24_fish3)	C++17	100 / 100	287 ms	57768 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=3e5+5;
ll N,Q,D,niz[maxn],pref[maxn],dod[maxn],fali[maxn],L[maxn],kol[maxn],ostalo[maxn],ostp[maxn],poc[maxn],res[maxn];
vector<int> koji[maxn];
int st[4*maxn],K;
int get(int lg,int dg,int gde=1,int lc=1,int dc=K){
   if(lg==lc and dg==dc)
      return st[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return get(lg,dg,gde*2,lc,sred);
   if(lg>sred)
      return get(lg,dg,gde*2+1,sred+1,dc);
   int v1,v2;
   v1=get(lg,sred,gde*2,lc,sred);
   v2=get(sred+1,dg,gde*2+1,sred+1,dc);
   return max(v1,v2);
}
vector<pair<int,ll>> V;
vector<ll> P;
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>D;
   K=1;
   while(K<N)
      K<<=1;
   for(int i=1;i<=N;i++)
      cin>>niz[i];
   for(int i=1;i<=N;i++)
      pref[i]=pref[i-1]+niz[i];
   for(int i=1;i<=N;i++)
      fali[i]=niz[i]%D;
   for(int i=1;i<=N;i++){
      kol[i]=kol[i-1];
      if(fali[i-1]>fali[i])
         kol[i]++;
      dod[i]=kol[i]*D+fali[i];
      ostalo[i]=(niz[i]-dod[i])/D;
      ostp[i]=ostp[i-1]+ostalo[i];
   }
   for(int i=1;i<=N;i++){
      int dg=1,gg=i,sred;
      while(dg<=gg){
         sred=(dg+gg)/2;
         if(dod[i]-kol[sred]*D<=niz[i]){
            L[i]=sred;
            gg=sred-1;
         }
         else
            dg=sred+1;
      }
   }

   for(int i=1;i<=N;i++)
      st[i+K-1]=L[i];
   for(int i=K-1;i>=1;i--)
      st[i]=max(st[i*2],st[i*2+1]);
  /* for(int i=1;i<=N;i++)
      cout<<ostalo[i]<<endl;*/

   int Q,l,r;
   cin>>Q;
   for(int i=1;i<=Q;i++){
      cin>>l>>r;
      if(get(l,r)>l){
         res[i]=-1;
         continue;
      }
      poc[i]=l;
      koji[r].push_back(i);
      /*ll suma=ostp[r]-ostp[l-1];
      suma-=ostalo[r]*(r-l+1);
      */
   }
   ll oduz=0;
   V.push_back({0,0});
   ostalo[0]=-9e18;
   P.push_back(0);
   for(int i=1;i<=N;i++){
      while(V.size()){
         if(ostalo[V.back().f]<ostalo[i])
            break;
         oduz-=V.back().s;
         V.pop_back();
         P.pop_back();
      }
      ll v=ostalo[i]*(i-V.back().f);
      P.push_back(P.back()+v);
      V.push_back({i,v});
      oduz+=v;

      for(int qind:koji[i]){
         int l=poc[qind];

         int dg=0,gg=V.size()-1,sred,poz;
         while(dg<=gg){
            sred=(dg+gg)/2;
            if(V[sred].f<l){
               poz=sred;
               dg=sred+1;
            }
            else
               gg=sred-1;
         }

         ll lv=-P[poz];
         poz++;

         lv-=(V[poz].f-V[poz-1].f)*ostalo[V[poz].f];
         lv+=ostalo[V[poz].f]*(V[poz].f-l+1);

         ll suma=ostp[i]-ostp[l-1];
         suma-=oduz+lv;
         if(suma<0)
            suma+=(1ll<<63);
         res[qind]=suma;
      }
   }
   for(int i=1;i<=Q;i++)
      cout<<res[i]<<"\n";
   return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:13: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |          poz++;
      |          ~~~^~

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