Submission #408844

# Submission time Handle Problem Language Result Execution time Memory
408844 2021-05-19T17:55:47 Z victoriad Fountain (eJOI20_fountain) C++14
60 / 100
1500 ms 28484 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<int>v;
 vector<int>d;
vector<vector<int> >up;
int search(int l,vector<int>&ps,int r){
	int low=0,hi=18,mid,re=-1;
	if(ps[up[r][1]]<=l)return r+1;
	while(low<=hi){
		mid=low+(hi-low)/2;
		if(ps[up[r][mid]]>l){
			low=mid+1;
			re=mid;
		}
		else{
			hi=mid-1;
		}
	}
	if(re==-1)return 0;
	return search(l,ps,up[r][re]);
}
 void suma(vector<int>&ps,vector<vector<int> >&c,int nodo){
	 if(up[nodo][1]==-1)ps[nodo]=v[nodo];
	 else ps[nodo]=ps[up[nodo][1]]+v[nodo];
	 for(int y:c[nodo]){
		 if(ps[y]==0){
			 suma(ps,c,y);
		 }
	 }
 }
 
int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
    int n,q;
    cin>>n>>q;
	int l,r;
    v.resize(n);
	d.resize(n);
    for(int i=0;i<n;i++){
      cin>>d[i]>>v[i];
    }
	vector<vector<int> >con(n);
	up.resize(n);
	vector<int>a(28,-1);
	for(int i=0;i<n;i++)up[i]=a;
	for(int i=0;i<n;i++)up[i][0]=i;
	int an=-1,u=0;
	for(int i=0;i<n;i++){
		bool b=true;
		int x=i+1;
		if(an!=-1 && d[i]>=u)x=an;
		for(int k=x;k<n;k++){
			if(d[i]<d[k]){
				up[i][1]=k;
				b=false;
				con[k].push_back(i);
				an=k;
				break;
			}
		}
		if(b){
			an=-1;
			up[i][1]=-1;
		}
		u=d[i];
 
	}
	vector<int>ps(n,0);
	for (int i=0;i<n;i++){
		if(up[i][1]==-1){
			suma(ps,con,i);
		}
	}
 
	for(int l=2;l<18;l++){
		for(int i=0;i<n;i++){
			if(up[i][l-1]!=-1)up[i][l]=up[up[i][l-1]][l-1];
		}
	}
 
	for(int i=0;i<q;i++){
		cin>>r>>l;
		r--;
		if(l<=v[r])cout<<r+1<<"\n";
		else if(ps[r]-l<0)cout<<0<<"\n";
		else cout<<search(ps[r]-l,ps,r)<<"\n";
	}
	
	
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 254 ms 26736 KB Output is correct
2 Correct 303 ms 24960 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 254 ms 26736 KB Output is correct
9 Correct 303 ms 24960 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 168 ms 13476 KB Output is correct
12 Correct 379 ms 28484 KB Output is correct
13 Correct 441 ms 23492 KB Output is correct
14 Correct 191 ms 22564 KB Output is correct
15 Execution timed out 1583 ms 19432 KB Time limit exceeded