oj.uz

답안 #408832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
408832 2021-05-19T17:39:51 Z victoriad Fountain (eJOI20_fountain) C++14
0 / 100
 1500 ms 20724 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(18,-1);
	for(int i=0;i<n;i++)up[i]=a;
	for(int i=0;i<n;i++)up[i][0]=i;
	
	int an=0,adim=0;
	for(int i=0;i<n;i++){
		bool b=true;
		int x,y;
		if(i==0){
			x=0;
			y=n;
		}
		else{
			if(d[i]>=adim){
				x=an;
				y=n;
			}
			else{
				x=i+1;
				y=an+1;
			}
		}
		for(int k=x;k<y;k++){
			if(d[i]<d[k]){
				up[i][1]=k;
				b=false;
				con[k].push_back(i);
				an=k;
				break;
			}
		}
		if(b){
			up[i][1]=-1;
		}
		adim=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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1597 ms 20724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -