Submission #1138222

#TimeUsernameProblemLanguageResultExecution timeMemory
1138222dacashewFish 3 (JOI24_fish3)C++20
20 / 100
698 ms85420 KiB
/* .... ...::--::::::.. .-+*#%%%%%%%*++=#%@@%%%%@@@%%%%%#+-: -*%%%%%%@%%%%@@@%%@@@@@@@@@@%%@@@%%%%##%#*- :*@%%@@@@@@%%@@@@@@@@@@@@@@@@@@@@%@@@@@%%%%%%%#- -#@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@%%@@@@@%%%%%%%#: .*@%%@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%@@@%%@@@@%%@%%%%@+ -#%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@%%@@@@@@@@%@@@%%%@+ -%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%%@@@@@@@@@@@@%%%@+ .%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@%@@@@@@@@+ .%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@@%@@%@@@@%@@@@= #@%@@@@@@@@@@@@@@@@@%%@@%%%%%%%%%%%%@%@%%%%@%%%%@%@@%%%@%%%@@%%. =@%@@@@@@@@@@@@@@@@@%%%%%%%%#%%%%%%%%%%%%%%%%%%@%%@@@@@%@%%%%@@%%. .@%%@%@@@@@@@@@@@%@%%%%#%%%##+**%%%%#%%%%###%%%%%%%@%%@@%%%%%%@@@@. -@%%%@@@@@@@@@@%%%%%%%#*#%#*++=++****++++++**#%###%@@@%@%%@%%%%@@@- -@%%@@@@@@@@@@%%#####%*+++====-=====------===+++=++#%@@@%%@%%%%%%%= .@%@%%@@@@@@@%##**+*+++==-----------------------===+*%%%@%%%%%%%%#. *@@@%@%@@@%#***+***++==--------------------===++===+#%%@@%%%%%%+- -%@@%@%@@%#****###%%%%#*+===---------==+**####**+++++#%%%%%%%%%: #@@%@%@%#*+++++++++++***+++===----===+++++========+++#%@%%%%%- -@@%@@@#+=+++++++=======++===-----=====++============+#@%%%@* .@@@@%@*===++**#*#@#%#++====-------===++#@%@**#*++==--+@%%%#: .##%@%%*====++**+=*#*-=++--=---------=+==+*+======----=@%*==- ++*#%%+==============-----=---:----------------------=%%==+= .+=+*%+==-----------:--------:::-----:::-----::::-----%#--=. -=+*%*===--------::::-------:::-::-:::::::::::::----=%+=-: ==+%#===------::::::--==---::::----::::::::::::----+#==: :++*#===--------:::---=----::::::--::::::::::::----++=- -=+#+===-------:--:-=-====---==---:::::::::::-----+-- ==++=====-------:--=+***+++++**+-:::::::::------==-. .==+====------------=++=========-::::::--------==:: =====----------=========------:::::-------== +======----=======----------------------==- :+==========++++**+=++===+++++=--------==+. =+==========***++=========++=--------===: =++=========++++==----=====-----======- -+++==========+++++++++==-----=======+: :*+++++=============--------==========: .*+**++++=======-----------======+++==: +++*****++++=================++++====: :++++++*****++++++++++++==++++++======- =%=+++++++******************+++====--===*- -%%=======+++++++++++++++++=======-----=-+#- -*%@++======++++++++==============------==+%*: =+*#%*+=======+++++++++==-========------===*#*+- .:****#%#*+========++++++++++=======------===+##++==-:. .-=+**#*#***##*++========================---======*#**++*++*++=-. .-=+##***#####***###*++==============-=--=====--======+#**+++++++*+++**+=: .-=*#####*##########*####*++==============--=============+#*#**++++++*****+*+**+-. .-+*#####################*#####+++==========================+***#****+++*+***********++= +###################*#############*++========================*#*******++++++*******+****** ####################*#############%**+===-===========--=====*#**#**+++++++++************** ###########################*##%@%%@%#*+=-----====--------=+*##*#@@@%#*++++++************** ########################**#%@@%%%%%%#%%#*=--------------+***#*#@%@@%%@%#++++***###******** ######################**#%%%%%%%%%%%%%%%%%#+--::::---=+#**###%@%%%%%%%%%@***#####***+***** ^^pavement for goodluck */ //Beichen is a classic problem in China #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; #define int long long #define test cout<<"test\n"<<flush; #define endl "\n" #define iloop(a,b) for(int i=a;i!=b;i+=(2*((int)(a<b))-1)) #define jloop(a,b) for(int j=a;j!=b;j+=(2*((int)(a<b))-1)) #define kloop(a,b) for(int k=a;k!=b;k+=(2*((int)(a<b))-1)) #define lloop(a,b) for(int l=a;l!=b;l+=(2*((int)(a<b))-1)) #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define pii pair<int,int> #define hashmap unordered_map #define coutpair(p) cout<<p.first<<" "<<p.second<<endl; #define couttrip(a,b,c) cout<<a<<" "<<b<<" "<<c<<" "; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define all(v) v.begin(),v.end() #define pii pair<int,int> #define flip(p) {p.second,p.first} #define lsb(x) x&-x #define debug(x) cout<<x<<flush #define decimal(x) fixed<<setprecision(x) #define sf(x) setprecision(x) #define mod(x,k) (((x%k)+k)%k) #define reset(a,v) for(auto &it:a){it=v;} #define inf 1e16 #define neginf -1e16 pair<int,int> rev(pair<int,int> p){return {p.second,p.first};} #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace __gnu_pbds; #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> //lb returns larger, ub returns larger or equals if set sorts backwards mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); struct node{ int s,e,mid; int mini,sum; node *l,*r; node(int S,int E){ s=S,e=E; mid=(S+E)/2; mini=0,sum=0; if(s!=e){ l=new node(s,mid); r=new node(mid+1,e); } } void update(int P,int V){ if(s==e){ mini=V,sum=V; return; } if(P<=mid){ l->update(P,V); } else{ r->update(P,V); } mini=min(l->mini,r->mini); sum=l->sum+r->sum; } int minquery(int S,int E){ if(s==S and e==E){ return mini; } if(E<=mid){ return l->minquery(S,E); } else if(S>mid){ return r->minquery(S,E); } else{ return min(l->minquery(S,mid),r->minquery(mid+1,E)); } } int sumquery(int S,int E){ if(s==S and e==E){ return sum; } if(E<=mid){ return l->sumquery(S,E); } else if(S>mid){ return r->sumquery(S,E); } else{ return l->sumquery(S,mid)+r->sumquery(mid+1,E); } } } *root; struct node1{ int s,e,mid; int mini; node1 *l,*r; node1(int S,int E){ s=S,e=E; mid=(S+E)/2; mini=0; if(s!=e){ l=new node1(s,mid); r=new node1(mid+1,e); } } void update(int P,int V){ if(s==e){ mini=V; return; } if(P<=mid){ l->update(P,V); } else{ r->update(P,V); } mini=min(l->mini,r->mini); } int query(int S,int E){ if(s==S and e==E){ return mini; } if(E<=mid){ return l->query(S,E); } else if(S>mid){ return r->query(S,E); } else{ return min(l->query(S,mid),r->query(mid+1,E)); } } } *root2; signed main(){ fastio; int n,d; cin>>n>>d; int a[n]; iloop(0,n){ cin>>a[i]; } int b[n]; b[n-1]=0; iloop(n-2,-1){ int prev=a[i+1]-d*b[i+1]; b[i]=(int)(max(a[i]-prev,0LL)+d-1)/d; } root=new node(0,n-1); root2=new node1(0,n-1); iloop(0,n){ root->update(i,b[i]); root2->update(i,a[i]-d*b[i]); //cout<<b[i]<<" "; } //cout<<endl; int q; cin>>q; iloop(0,q){ int a,b; cin>>a>>b; a--,b--; int x=root->minquery(a,b); int y=root2->query(a,b); //cout<<x<<" "<<y<<" "; if(y+d*x<0){ cout<<-1<<endl; } else{ cout<<root->sumquery(a,b)-(b-a+1)*x<<endl;; } } }
#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...