oj.uz

답안 #408826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
408826 2021-05-19T17:22:55 Z victoriad Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 31748 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;
	for(int i=0;i<n;i++){
		bool b=true;
		for(int k=i+1;k<n;k++){
			if(d[i]<d[k]){
				up[i][1]=k;
				b=false;
				con[k].push_back(i);
				break;
			}
		}
		if(b){
			up[i][1]=-1;
		}
 
	}
	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

# 결과 실행 시간 메모리 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 452 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

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 26008 KB Output is correct
2 Correct 281 ms 27192 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 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 452 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 245 ms 26008 KB Output is correct
9 Correct 281 ms 27192 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 249 ms 14420 KB Output is correct
12 Correct 387 ms 31748 KB Output is correct
13 Correct 709 ms 26388 KB Output is correct
14 Correct 186 ms 24772 KB Output is correct
15 Execution timed out 1594 ms 19772 KB Time limit exceeded