Submission #407222

#	Time	Username	Problem	Language	Result	Execution time	Memory
407222		victoriad	Fountain (eJOI20_fountain)	C++14	0 / 100	237 ms	524292 KiB

fountain

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
 vector<long long int>v;
	vector<int>orden;
 void dfs(int nodo,vector<pair<int,long long int> >&nuevo,vector<int>&grupo,int cc,vector<int>con,int x){
	 grupo[nodo]=cc;
	 orden[nodo]=x;
	 if(nuevo.size()==0){
		 pair<int,int>p=make_pair(nodo,v[nodo]);
		 nuevo.push_back(p);
	 }
	 else{
		 pair<int,int>p=make_pair(nodo,v[nodo]+nuevo[nuevo.size()-1].second);
			nuevo.push_back(p);	
	 }
	 if(grupo[con[nodo]]==-1){
		 dfs(con[nodo],nuevo,grupo,cc,con,x+1);
	 }
 }

 int search(int l,vector<pair<int,long long int> >c,int o){
	 int low=o,hi=c.size(),r=-1,mid;
	 while(low<=hi){
		 mid=low+(hi-low)/2;
		 if((c[mid].second-c[o].second+v[o])>=l){
			 r=mid;
			 hi=mid-1;
		 }
		 else{
			 low=mid+1;
		 }

	 }
	 if(r==-1)return 0;
	 else return c[r].first+1;
 }
 
int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
    int n,q;
    cin>>n>>q;
    int vo,r,l;
   	v.resize(n);
    vector<long long int>d(n);
    for(int i=0;i<n;i++){
      cin>>d[i]>>v[i];
    }
	vector<int>con(n);
	for(int i=0;i<n;i++){
		bool b=false;
		for(int k=i;k<n;k++){
			if(d[i]<d[k]){
				con[i]=k;
				b=true;
				break;
			}
		}
		if(!b)con[i]=-1;
	}
	vector<vector<pair<int,long long int> > >compo;
	vector<int>grupo(n,-1);
	int cc=0;
	orden.resize(n);
	for(int i=0;i<n;i++){
		if(grupo[i]==-1){
			vector<pair<int,long long int> >nuevo;
			dfs(i,nuevo,grupo,cc,con,0);
			compo.push_back(nuevo);
			cc++;
		}
	}

    
    for(int i=0;i<q;i++){
      cin>>r>>l;
      r--;
	  if(l<=v[r])cout<<r+1<<"\n";
	  else
      cout<<search(l,compo[grupo[r]],orden[r])<<"\n";
    }
  return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:53:9: warning: unused variable 'vo' [-Wunused-variable]
   53 |     int vo,r,l;
      |         ^~

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