oj.uz

Submission #817855

# Submission time Handle Problem Language Result Execution time Memory
817855 2023-08-09T18:07:08 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 135 ms 20220 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()
const int MAXN=1e5+100;
const int LOGN=17;
int n;
int up[MAXN][LOGN+1];
int arr[MAXN];
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];
}
arr[n+1]=(int)1e9+100;
stack<pair<int,int>> st;
int ne[n+1];
memset(ne,n+1,sizeof(ne));
for(int i=1;i<=n+1;i++){
	while(!st.empty()&&arr[st.top().F]<arr[i]){
		ne[st.top().F]=i;
		st.pop();
	}
	st.push({i,arr[i]});
}
// for(int i=1;i<=n;i++) dbg(i,ne[i]);
#pragma GCC ivdep
for(int i=1;i<=n;i++){
	int x=ne[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 5 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 19392 KB Output is correct
2 Correct 95 ms 18892 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 5 ms 10580 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 90 ms 19392 KB Output is correct
9 Correct 95 ms 18892 KB Output is correct
10 Correct 5 ms 10452 KB Output is correct
11 Correct 52 ms 13116 KB Output is correct
12 Correct 135 ms 20220 KB Output is correct
13 Correct 118 ms 15476 KB Output is correct
14 Correct 97 ms 14520 KB Output is correct
15 Correct 82 ms 13716 KB Output is correct