oj.uz

Submission #408855

# Submission time Handle Problem Language Result Execution time Memory
408855 2021-05-19T18:08:05 Z victoriad Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 28116 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;
	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;
	if(ps[up[r][1]]<=l)return up[r][re]+1;
	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]){
			 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;
	up[n-1][1]=-1;
	bool bo=true;
	int x=d[n-1];
	for(int i=n-2;i>=0;i++){
		if(x>d[i]){
			bo=false;
			break;
		}
	}
	if(!bo){
	for(int i=0;i<n-1;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;
}

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 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 26308 KB Output is correct
2 Correct 295 ms 24504 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 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 285 ms 26308 KB Output is correct
9 Correct 295 ms 24504 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 174 ms 13112 KB Output is correct
12 Correct 393 ms 28116 KB Output is correct
13 Correct 484 ms 23108 KB Output is correct
14 Correct 193 ms 22188 KB Output is correct
15 Execution timed out 1557 ms 19056 KB Time limit exceeded