oj.uz

Submission #817822

# Submission time Handle Problem Language Result Execution time Memory
817822 2023-08-09T17:13:08 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 240 ms 52832 KB 
#include <iostream>
#include <vector>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#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;
	#pragma GCC ivdep
	for(int i=1;i<=LOGN;i++) 
		up[node][i]=up[up[node][i-1]][i-1];
	#pragma GCC ivdep
	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));
#pragma GCC ivdep
for(int i=1;i<=n;i++){
	cin>>arr[i]>>v[i];
}
build(1,1,n);
#pragma GCC ivdep
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);
#pragma GCC ivdep
while(q--){
	int node,k;
	cin>>node>>k;
	int nn=node;
	#pragma GCC ivdep
	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 15 ms 40916 KB Output is correct
2 Correct 14 ms 41044 KB Output is correct
3 Correct 15 ms 41052 KB Output is correct
4 Correct 15 ms 41104 KB Output is correct
5 Correct 18 ms 41148 KB Output is correct
6 Correct 16 ms 41044 KB Output is correct
7 Correct 15 ms 41036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 52012 KB Output is correct
2 Correct 161 ms 51392 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 40916 KB Output is correct
2 Correct 14 ms 41044 KB Output is correct
3 Correct 15 ms 41052 KB Output is correct
4 Correct 15 ms 41104 KB Output is correct
5 Correct 18 ms 41148 KB Output is correct
6 Correct 16 ms 41044 KB Output is correct
7 Correct 15 ms 41036 KB Output is correct
8 Correct 150 ms 52012 KB Output is correct
9 Correct 161 ms 51392 KB Output is correct
10 Correct 15 ms 41044 KB Output is correct
11 Correct 80 ms 44992 KB Output is correct
12 Correct 240 ms 52832 KB Output is correct
13 Correct 179 ms 48592 KB Output is correct
14 Correct 150 ms 47652 KB Output is correct
15 Correct 125 ms 46872 KB Output is correct