oj.uz

Submission #407336

# Submission time Handle Problem Language Result Execution time Memory
407336 2021-05-18T18:26:16 Z victoriad Fountain (eJOI20_fountain) C++14
60 / 100
 1215 ms 524292 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4512 KB Output is correct
2 Correct 98 ms 4368 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 88 ms 4512 KB Output is correct
9 Correct 98 ms 4368 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Runtime error 1215 ms 524292 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -