oj.uz

답안 #817820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817820 2023-08-09T17:11:07 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 246 ms 52788 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5;
const int LOGN=20;
int n;
int up[MAXN][LOGN+1];
int arr[MAXN];
int tree[4*MAXN];
void build(int node,int l,int r){
	if(l==r) {
		tree[node]=arr[l];
		return;
	}
	int mid=(l+r)/2;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
int query(int node,int l,int r,int ql,int x){
	if(l==r){
		return (tree[node]>x&&l>=ql)?l:n+1;
	}
	int mid=(l+r)/2;
	if(ql<=mid){
		if(tree[node<<1]<x)
			return query(node<<1|1,mid+1,r,ql,x);
		int left=query(node<<1,l,mid,ql,x);
		if(left==n+1) 
			return query(node<<1|1,mid+1,r,ql,x);
		return left;
	}
	return query(node<<1|1,mid+1,r,ql,x);
}
vector<vector<pair<int,int>>> c(MAXN);
int depth[MAXN];
void dfs(int node,int par,ll ew=0){
	depth[node]=depth[par]+ew;
	up[node][0]=par;
	for(int i=1;i<=LOGN;i++) 
		up[node][i]=up[up[node][i-1]][i-1];
	for(auto x:c[node]){
		if(x.F==par) continue;
		dfs(x.F,node,x.S);
	}
}
signed main(){
	memset(depth,0,sizeof(depth));
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int q;
cin>>n>>q;
int v[MAXN+1];
memset(up,n+1,sizeof(up));
for(int i=1;i<=n;i++){
	cin>>arr[i]>>v[i];
}
build(1,1,n);
for(int i=1;i<=n;i++){
	int x=query(1,1,n,i,arr[i]);
	int weight=v[i];
	c[x].pb({i,weight});
}
dfs(n+1,n+1);
while(q--){
	int node,k;
	cin>>node>>k;
	int nn=node;
	for(int i=LOGN;i>=0;i--){
		if(depth[nn]-depth[up[node][i]]<k){
			node=up[node][i];
		}
	}
	if(node==n+1) cout<<0<<endl;
	else cout<<node<<endl;
	// dbg(node);
}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 40916 KB Output is correct
2 Correct 15 ms 40980 KB Output is correct
3 Correct 16 ms 41008 KB Output is correct
4 Correct 16 ms 41044 KB Output is correct
5 Correct 17 ms 41128 KB Output is correct
6 Correct 15 ms 41016 KB Output is correct
7 Correct 16 ms 41044 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 51984 KB Output is correct
2 Correct 201 ms 51464 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 40916 KB Output is correct
2 Correct 15 ms 40980 KB Output is correct
3 Correct 16 ms 41008 KB Output is correct
4 Correct 16 ms 41044 KB Output is correct
5 Correct 17 ms 41128 KB Output is correct
6 Correct 15 ms 41016 KB Output is correct
7 Correct 16 ms 41044 KB Output is correct
8 Correct 166 ms 51984 KB Output is correct
9 Correct 201 ms 51464 KB Output is correct
10 Correct 16 ms 41088 KB Output is correct
11 Correct 84 ms 44968 KB Output is correct
12 Correct 246 ms 52788 KB Output is correct
13 Correct 197 ms 50528 KB Output is correct
14 Correct 154 ms 50536 KB Output is correct
15 Correct 129 ms 50204 KB Output is correct