Submission #407336

#	Time	Username	Problem	Language	Result	Execution time	Memory
407336		victoriad	Fountain (eJOI20_fountain)	C++14	60 / 100	1215 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;
int search(int l,vector<pair<int,int> >&p,int o,int n){
	int lo=o,hi=p.size(),mid,r=-1;
	int x;
	if(o==0)x=0;
	else x=p[o-1].second;
	if(l>p.back().second-x)return 0;
	while(lo<=hi){
		mid=lo+(hi-lo)/2;
		if(p[mid].second-x>=l){
			r=mid;
			hi=mid-1;
		}
		else{
			lo=mid+1;
		}
	}
	if(r==-1)return 0;
	else return p[r].first+1;
}
void dfs(int nodo,vector<pair<int,int> >&p,vector<int>&g,int cc,vector<int>&c,int x){
	g[nodo]=cc;
	orden[nodo]=x;
	x++;
	if(p.size()==0){
		p.push_back(make_pair(nodo,v[nodo]));
	}
	else{
			p.push_back(make_pair(nodo,p.back().second+v[nodo]));
	}
	if(c[nodo]!=-1)dfs(c[nodo],p,g,cc,c,x);
}
int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
    int n,q;
    cin>>n>>q;
	int l,r;
    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;
	}
	int cc=0;
	vector<int>g(n,-1);
	orden.resize(n);
	vector<vector<pair<int,int> > >c;
	for(int i=0;i<n;i++){
		if(g[i]==-1){
			vector<pair<int,int> >p;
			dfs(i,p,g,cc,con,0);
			c.push_back(p);
			cc++;
		}
	}
    for(int i=0;i<q;i++){
      cin>>r>>l;
      r--;
      if(l<=v[r])cout<<r+1<<"\n";
	  else{
		 cout<<search(l,c[g[r]],orden[r],r)<<"\n";
	  }
    }
  return 0;
}

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