oj.uz

Submission #817830

# Submission time Handle Problem Language Result Execution time Memory
817830 2023-08-09T17:29:57 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 193 ms 28996 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=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)1e18+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 8 ms 18384 KB Output is correct
2 Correct 8 ms 18388 KB Output is correct
3 Correct 8 ms 18388 KB Output is correct
4 Correct 8 ms 18388 KB Output is correct
5 Correct 9 ms 18388 KB Output is correct
6 Correct 8 ms 18388 KB Output is correct
7 Correct 9 ms 18312 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 28348 KB Output is correct
2 Correct 143 ms 27512 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18384 KB Output is correct
2 Correct 8 ms 18388 KB Output is correct
3 Correct 8 ms 18388 KB Output is correct
4 Correct 8 ms 18388 KB Output is correct
5 Correct 9 ms 18388 KB Output is correct
6 Correct 8 ms 18388 KB Output is correct
7 Correct 9 ms 18312 KB Output is correct
8 Correct 123 ms 28348 KB Output is correct
9 Correct 143 ms 27512 KB Output is correct
10 Correct 10 ms 18388 KB Output is correct
11 Correct 69 ms 21844 KB Output is correct
12 Correct 193 ms 28996 KB Output is correct
13 Correct 144 ms 25020 KB Output is correct
14 Correct 110 ms 24004 KB Output is correct
15 Correct 95 ms 23932 KB Output is correct