oj.uz

Submission #817850

# Submission time Handle Problem Language Result Execution time Memory
817850 2023-08-09T18:03:28 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 338 ms 38360 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 sm[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=0;i<=LOGN;i++){
    for(int node=0;node<MAXN;node++) up[node][i]=n+1,sm[node][i]=0;
}
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]);
// memset(sm,0,sizeof(sm));
#pragma GCC ivdep
for(int i=1;i<=n;i++){
	int x=ne[i];
	int weight=v[i];
	up[i][0]=x;
	sm[i][0]=weight;
}
int i=1,node=1;
for(i=1;i<LOGN;i++){
    for(node=1;node<=n;node++){
   	// 	dbg(node,i,up[node][i-1]);
		up[node][i]=up[up[node][i-1]][i-1];
		sm[node][i]=sm[node][i-1]+sm[up[node][i-1]][i-1];
	   // dbg(node,i,up[node][i],sm[node][i]);

	}
}
// dfs(n+1,n+1);
#pragma GCC ivdep
while(q--){
	int node,k;
	cin>>node>>k;
	int nn=node;
// 	k-=v[node];
	// #pragma GCC ivdep
	for(int i=LOGN-1;i>=0;i--){
		if(sm[node][i]<k){
		    k-=sm[node][i];
			node=up[node][i];
		}
	}
	if(node==n+1) {
	    cout<<0<<endl;
	    continue;
	}
	cout<<node<<endl;
    // if(k>0")
// 	dbg(k,node);
}
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:103:6: warning: unused variable 'nn' [-Wunused-variable]
  103 |  int nn=node;
      |      ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32340 KB Output is correct
2 Correct 15 ms 32468 KB Output is correct
3 Correct 13 ms 32392 KB Output is correct
4 Correct 13 ms 32468 KB Output is correct
5 Correct 13 ms 32428 KB Output is correct
6 Correct 16 ms 32432 KB Output is correct
7 Correct 16 ms 32396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 37472 KB Output is correct
2 Correct 197 ms 36032 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32340 KB Output is correct
2 Correct 15 ms 32468 KB Output is correct
3 Correct 13 ms 32392 KB Output is correct
4 Correct 13 ms 32468 KB Output is correct
5 Correct 13 ms 32428 KB Output is correct
6 Correct 16 ms 32432 KB Output is correct
7 Correct 16 ms 32396 KB Output is correct
8 Correct 213 ms 37472 KB Output is correct
9 Correct 197 ms 36032 KB Output is correct
10 Correct 12 ms 32384 KB Output is correct
11 Correct 76 ms 35288 KB Output is correct
12 Correct 338 ms 36508 KB Output is correct
13 Correct 171 ms 38192 KB Output is correct
14 Correct 134 ms 36628 KB Output is correct
15 Correct 118 ms 38360 KB Output is correct