oj.uz

Submission #408850

# Submission time Handle Problem Language Result Execution time Memory
408850 2021-05-19T18:01:45 Z victoriad Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 28380 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;
	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 452 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 26524 KB Output is correct
2 Correct 319 ms 24680 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 452 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 452 KB Output is correct
8 Correct 314 ms 26524 KB Output is correct
9 Correct 319 ms 24680 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 175 ms 13196 KB Output is correct
12 Correct 443 ms 28380 KB Output is correct
13 Correct 474 ms 23272 KB Output is correct
14 Correct 190 ms 22264 KB Output is correct
15 Execution timed out 1571 ms 19216 KB Time limit exceeded