제출 #1065944

#제출 시각아이디문제언어결과실행 시간메모리
1065944NemanjaSo2005Fish 3 (JOI24_fish3)C++17
100 / 100
287 ms57768 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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