Submission #1138222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138222		dacashew	Fish 3 (JOI24_fish3)	C++20	20 / 100	698 ms	85420 KiB

Main

/*                                    
                                     ....     ...::--::::::..                             
                              .-+*#%%%%%%%*++=#%@@%%%%@@@%%%%%#+-:                        
                          -*%%%%%%@%%%%@@@%%@@@@@@@@@@%%@@@%%%%##%#*-                     
                       :*@%%@@@@@@%%@@@@@@@@@@@@@@@@@@@@%@@@@@%%%%%%%#-                   
                     -#@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@%%@@@@@%%%%%%%#:                 
                   .*@%%@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%@@@%%@@@@%%@%%%%@+                
                  -#%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@%%@@@@@@@@%@@@%%%@+               
                 -%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%%@@@@@@@@@@@@%%%@+              
                .%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@%@@@@@@@@+             
               .%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@@%@@%@@@@%@@@@=            
               #@%@@@@@@@@@@@@@@@@@%%@@%%%%%%%%%%%%@%@%%%%@%%%%@%@@%%%@%%%@@%%.           
              =@%@@@@@@@@@@@@@@@@@%%%%%%%%#%%%%%%%%%%%%%%%%%%@%%@@@@@%@%%%%@@%%.          
             .@%%@%@@@@@@@@@@@%@%%%%#%%%##+**%%%%#%%%%###%%%%%%%@%%@@%%%%%%@@@@.          
             -@%%%@@@@@@@@@@%%%%%%%#*#%#*++=++****++++++**#%###%@@@%@%%@%%%%@@@-          
             -@%%@@@@@@@@@@%%#####%*+++====-=====------===+++=++#%@@@%%@%%%%%%%=          
             .@%@%%@@@@@@@%##**+*+++==-----------------------===+*%%%@%%%%%%%%#.          
              *@@@%@%@@@%#***+***++==--------------------===++===+#%%@@%%%%%%+-           
              -%@@%@%@@%#****###%%%%#*+===---------==+**####**+++++#%%%%%%%%%:            
               #@@%@%@%#*+++++++++++***+++===----===+++++========+++#%@%%%%%-             
               -@@%@@@#+=+++++++=======++===-----=====++============+#@%%%@*              
               .@@@@%@*===++**#*#@#%#++====-------===++#@%@**#*++==--+@%%%#:              
               .##%@%%*====++**+=*#*-=++--=---------=+==+*+======----=@%*==-              
                ++*#%%+==============-----=---:----------------------=%%==+=              
                .+=+*%+==-----------:--------:::-----:::-----::::-----%#--=.              
                 -=+*%*===--------::::-------:::-::-:::::::::::::----=%+=-:               
                  ==+%#===------::::::--==---::::----::::::::::::----+#==:                
                  :++*#===--------:::---=----::::::--::::::::::::----++=-                 
                   -=+#+===-------:--:-=-====---==---:::::::::::-----+--                  
                    ==++=====-------:--=+***+++++**+-:::::::::------==-.                  
                    .==+====------------=++=========-::::::--------==::                   
                        =====----------=========------:::::-------==                      
                         +======----=======----------------------==-                      
                         :+==========++++**+=++===+++++=--------==+.                      
                          =+==========***++=========++=--------===:                       
                           =++=========++++==----=====-----======-                        
                           -+++==========+++++++++==-----=======+:                        
                           :*+++++=============--------==========:                        
                           .*+**++++=======-----------======+++==:                        
                            +++*****++++=================++++====:                        
                           :++++++*****++++++++++++==++++++======-                        
                          =%=+++++++******************+++====--===*-                      
                         -%%=======+++++++++++++++++=======-----=-+#-                     
                        -*%@++======++++++++==============------==+%*:                    
                       =+*#%*+=======+++++++++==-========------===*#*+-                   
                    .:****#%#*+========++++++++++=======------===+##++==-:.               
               .-=+**#*#***##*++========================---======*#**++*++*++=-.          
          .-=+##***#####***###*++==============-=--=====--======+#**+++++++*+++**+=:      
      .-=*#####*##########*####*++==============--=============+#*#**++++++*****+*+**+-.  
  .-+*#####################*#####+++==========================+***#****+++*+***********++=
+###################*#############*++========================*#*******++++++*******+******
####################*#############%**+===-===========--=====*#**#**+++++++++**************
###########################*##%@%%@%#*+=-----====--------=+*##*#@@@%#*++++++**************
########################**#%@@%%%%%%#%%#*=--------------+***#*#@%@@%%@%#++++***###********
######################**#%%%%%%%%%%%%%%%%%#+--::::---=+#**###%@%%%%%%%%%@***#####***+*****
^^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;;
		}
	}
}

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