oj.uz

Submission #788822

# Submission time Handle Problem Language Result Execution time Memory
788822 2023-07-20T16:21:28 Z ThylOne Fountain (eJOI20_fountain) C++14
100 / 100
 901 ms 34640 KB 
    #include <bits/stdc++.h>
    using namespace std;
    #define debug(var) cerr<<"#"<<#var<<"="<<var<<endl;
    #define int long long
    const int LOG = 18;
    const int MAXI = 2*100000;
    struct Recip{
    	int diametre;
    	int capacite;
    	int id;
    	void read(int i){
    		cin>>diametre;
    		cin>>capacite;
    		id=i;
    	};
    };
    vector<Recip> recipient;
    vector<int> links[MAXI];
    int sumFromRoot[MAXI];
    int up[MAXI][LOG];
    int n,q;
     
    void dfs(int node,int somme=0){
    	somme+=recipient[node].capacite;
    	sumFromRoot[node] = somme;
    	for(int&v:links[node]){
    		dfs(v,somme);
    	}
    }
    int ancestorK(int node,int k){
    	for(int log=LOG-1;log>=0;log--){
			if(node==-1)return -1;
    		if((k>>log)&1){
    			node = up[node][log];
    		}
    	}
    	return node;
    }
     
     
    int solve2(int id,int volume){
    	int sommeChaine = sumFromRoot[id];
    	if(sommeChaine<volume){
    		return -1;
    	}
    	int low=0;
    	int high=n-1;
    	while((high-low)>1){
    		int mid = (low+high)/2;
    		int pos = ancestorK(id,mid);
    		if(pos==-1){
    			high=mid;
    			continue;
    		}
    		int somme = sommeChaine-sumFromRoot[pos]+recipient[pos].capacite;
    		if(somme>volume){
    			high = mid;
    		}else if(somme<volume){
    			low = mid;			
    		}else{
    			return pos;
    		}
    	}
    	int LS = sommeChaine-sumFromRoot[ancestorK(id,low)]+recipient[ancestorK(id,low)].capacite;
    	if(LS>=volume){
    		return ancestorK(id,low);
    	}else{
    		return ancestorK(id,high);
    	}
    }
    signed main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
       
    	cin>>n>>q;
    	recipient.resize(n);
    	vector<int> pref(n);
    	int act=0;
    	for(int i = 0 ; i <n;i++){
    		recipient[i].read(i);
    		act+=recipient[i].capacite;
    		pref[i]=act;
    	}
    	int papa[n];
    	for(int i = 0;i<n;i++){
    		papa[i]=-1;
    	}
     
    	stack<Recip> pile;
    	for(int i = 0;i<n;i++){
    		while(!pile.empty() && recipient[i].diametre>pile.top().diametre){
    			papa[pile.top().id] = i;
    			links[i].push_back(pile.top().id);
    			pile.pop();
    		}
    		pile.push(recipient[i]);
    	}
    	for(int i = 0 ; i<n;i++){
    		if(papa[i]==-1){
    			dfs(i);
    		}
    		up[i][0]=papa[i];
    	}
    	for(int l=1;l<LOG;l++){
    		for(int i=0;i<n;i++){
    			if(up[i][l-1]==-1){
    				up[i][l]=-1;
    			}else{
    				up[i][l] = up[up[i][l-1]][l-1];
    			}
    			
    		}
    	}
    	for(int i = 0 ; i < q;i++){
    		int id,volume;cin>>id>>volume;
    		id--;
    		cout<<solve2(id,volume)+1<<endl;
    	}
    	
    	
       
    }

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 6 ms 5204 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 29104 KB Output is correct
2 Correct 656 ms 30476 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 6 ms 5204 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 531 ms 29104 KB Output is correct
9 Correct 656 ms 30476 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 235 ms 19180 KB Output is correct
12 Correct 901 ms 34640 KB Output is correct
13 Correct 575 ms 31212 KB Output is correct
14 Correct 373 ms 29920 KB Output is correct
15 Correct 315 ms 31056 KB Output is correct