제출 #909887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909887		dacashew	Fountain (eJOI20_fountain)	C++14	100 / 100	202 ms	32848 KiB

fountain

/*                                    
                                     ....     ...::--::::::..                             
                              .-+*#%%%%%%%*++=#%@@%%%%@@@%%%%%#+-:                        
                          -*%%%%%%@%%%%@@@%%@@@@@@@@@@%%@@@%%%%##%#*-                     
                       :*@%%@@@@@@%%@@@@@@@@@@@@@@@@@@@@%@@@@@%%%%%%%#-                   
                     -#@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@%%@@@@@%%%%%%%#:                 
                   .*@%%@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%@@@%%@@@@%%@%%%%@+                
                  -#%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@%%@@@@@@@@%@@@%%%@+               
                 -%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%%@@@@@@@@@@@@%%%@+              
                .%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@%@@@@@@@@+             
               .%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@@%@@%@@@@%@@@@=            
               #@%@@@@@@@@@@@@@@@@@%%@@%%%%%%%%%%%%@%@%%%%@%%%%@%@@%%%@%%%@@%%.           
              =@%@@@@@@@@@@@@@@@@@%%%%%%%%#%%%%%%%%%%%%%%%%%%@%%@@@@@%@%%%%@@%%.          
             .@%%@%@@@@@@@@@@@%@%%%%#%%%##+**%%%%#%%%%###%%%%%%%@%%@@%%%%%%@@@@.          
             -@%%%@@@@@@@@@@%%%%%%%#*#%#*++=++****++++++**#%###%@@@%@%%@%%%%@@@-          
             -@%%@@@@@@@@@@%%#####%*+++====-=====------===+++=++#%@@@%%@%%%%%%%=          
             .@%@%%@@@@@@@%##**+*+++==-----------------------===+*%%%@%%%%%%%%#.          
              *@@@%@%@@@%#***+***++==--------------------===++===+#%%@@%%%%%%+-           
              -%@@%@%@@%#****###%%%%#*+===---------==+**####**+++++#%%%%%%%%%:            
               #@@%@%@%#*+++++++++++***+++===----===+++++========+++#%@%%%%%-             
               -@@%@@@#+=+++++++=======++===-----=====++============+#@%%%@*              
               .@@@@%@*===++**#*#@#%#++====-------===++#@%@**#*++==--+@%%%#:              
               .##%@%%*====++**+=*#*-=++--=---------=+==+*+======----=@%*==-              
                ++*#%%+==============-----=---:----------------------=%%==+=              
                .+=+*%+==-----------:--------:::-----:::-----::::-----%#--=.              
                 -=+*%*===--------::::-------:::-::-:::::::::::::----=%+=-:               
                  ==+%#===------::::::--==---::::----::::::::::::----+#==:                
                  :++*#===--------:::---=----::::::--::::::::::::----++=-                 
                   -=+#+===-------:--:-=-====---==---:::::::::::-----+--                  
                    ==++=====-------:--=+***+++++**+-:::::::::------==-.                  
                    .==+====------------=++=========-::::::--------==::                   
                        =====----------=========------:::::-------==                      
                         +======----=======----------------------==-                      
                         :+==========++++**+=++===+++++=--------==+.                      
                          =+==========***++=========++=--------===:                       
                           =++=========++++==----=====-----======-                        
                           -+++==========+++++++++==-----=======+:                        
                           :*+++++=============--------==========:                        
                           .*+**++++=======-----------======+++==:                        
                            +++*****++++=================++++====:                        
                           :++++++*****++++++++++++==++++++======-                        
                          =%=+++++++******************+++====--===*-                      
                         -%%=======+++++++++++++++++=======-----=-+#-                     
                        -*%@++======++++++++==============------==+%*:                    
                       =+*#%*+=======+++++++++==-========------===*#*+-                   
                    .:****#%#*+========++++++++++=======------===+##++==-:.               
               .-=+**#*#***##*++========================---======*#**++*++*++=-.          
          .-=+##***#####***###*++==============-=--=====--======+#**+++++++*+++**+=:      
      .-=*#####*##########*####*++==============--=============+#*#**++++++*****+*+**+-.  
  .-+*#####################*#####+++==========================+***#****+++*+***********++=
+###################*#############*++========================*#*******++++++*******+******
####################*#############%**+===-===========--=====*#**#**+++++++++**************
###########################*##%@%%@%#*+=-----====--------=+*##*#@@@%#*++++++**************
########################**#%@@%%%%%%#%%#*=--------------+***#*#@%@@%%@%#++++***###********
######################**#%%%%%%%%%%%%%%%%%#+--::::---=+#**###%@%%%%%%%%%@***#####***+*****
^^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 exit return 0	
#define iloop(n) for(int i=0;i<n;i++)
#define jloop(n) for(int j=0;j<n;j++)
#define kloop(n) for(int k=0;k<n;k++)
#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>
#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, greater<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>
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
const int NMAX=100005;
int c[NMAX];
int d[NMAX];
vector<int> v[NMAX];
int mem[NMAX][20];
int depth[NMAX];
void dfs(int cur,int par,int d){
	depth[cur]=d;
	mem[cur][0]=par;
	iloop(18){
		int h=mem[cur][i];
		if(h==-1){
			continue;
		}
		mem[cur][i+1]=mem[h][i];
	}
	for(auto it:v[cur]){
		if(it!=par){
			dfs(it,cur,d+c[it]);
		}
	}
}
int query(int cur,int k){
	if(cur==-1){
		return -1;
	}
	iloop(19){
		if(((1<<i)&k)==0){
			continue;
		}
		cur=mem[cur][i];
		if(cur==-1){
			return -1;
		}
	}
	return cur;
}
int range(int a,int b){
	if(b==-1 or mem[b][0]==-1){
		return depth[a];
	}
	return depth[a]-depth[mem[b][0]];
}
signed main(){
	fastio
	int n,q;
	cin>>n>>q;
	iloop(n){
		cin>>d[i]>>c[i];
	}
	stack<int> s;
	iloop(n){
		if(s.empty()){
			s.push(i);
			continue;
		}
		while(!s.empty() and d[s.top()]<d[i]){
			v[i].pb(s.top());
			v[s.top()].pb(i);
			s.pop();
		}
		s.push(i);
	}
	while(!s.empty()){
		v[n].pb(s.top());
		v[s.top()].pb(n);
		s.pop();
	}
	memset(mem,-1,sizeof(mem));
	dfs(n,-1,0);
	/*iloop(n+1){
		cout<<depth[i]<<" ";
	}
	cout<<endl;
	iloop(n){
		jloop(19){
			cout<<mem[i][j]<<" ";
		}
		cout<<endl;
	}*/
	//depth[n]=INT_MAX;
	iloop(q){
		int a,b;
		cin>>a>>b;
		a--;
		if(c[a]>=b){
			cout<<a+1<<endl;
			continue;
		}
		int s=a;
		for(int i=19;i>=0;i--){
			int temp=-1;
			if(a!=-1) temp=mem[a][i];
			if(range(s,temp)<b){
				a=temp;
			}
		}
		if(a==-1 or mem[a][0]==-1){
			cout<<0<<endl;
		} else{
			cout<<mem[a][0]+1<<endl;
		}
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40