oj.uz

Submission #817819

# Submission time Handle Problem Language Result Execution time Memory
817819 2023-08-09T17:09:44 Z YassirSalama Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 56868 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){
		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

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40916 KB Output is correct
2 Correct 16 ms 41048 KB Output is correct
3 Correct 18 ms 41064 KB Output is correct
4 Correct 16 ms 41044 KB Output is correct
5 Correct 16 ms 41172 KB Output is correct
6 Correct 17 ms 41096 KB Output is correct
7 Correct 17 ms 41012 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 53468 KB Output is correct
2 Correct 180 ms 54508 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 40916 KB Output is correct
2 Correct 16 ms 41048 KB Output is correct
3 Correct 18 ms 41064 KB Output is correct
4 Correct 16 ms 41044 KB Output is correct
5 Correct 16 ms 41172 KB Output is correct
6 Correct 17 ms 41096 KB Output is correct
7 Correct 17 ms 41012 KB Output is correct
8 Correct 195 ms 53468 KB Output is correct
9 Correct 180 ms 54508 KB Output is correct
10 Correct 17 ms 41044 KB Output is correct
11 Correct 592 ms 46760 KB Output is correct
12 Correct 298 ms 56868 KB Output is correct
13 Execution timed out 1581 ms 49144 KB Time limit exceeded
14 Halted 0 ms 0 KB -