oj.uz

답안 #817854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817854 2023-08-09T18:06:25 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 156 ms 20252 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 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)1e9+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:102:6: warning: unused variable 'nn' [-Wunused-variable]
  102 |  int nn=node;
      |      ^~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 8 ms 17492 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 9 ms 17492 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 9 ms 17556 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 18956 KB Output is correct
2 Correct 104 ms 19016 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 8 ms 17492 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 9 ms 17492 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 9 ms 17556 KB Output is correct
8 Correct 98 ms 18956 KB Output is correct
9 Correct 104 ms 19016 KB Output is correct
10 Correct 9 ms 17492 KB Output is correct
11 Correct 56 ms 18484 KB Output is correct
12 Correct 156 ms 19436 KB Output is correct
13 Correct 117 ms 19484 KB Output is correct
14 Correct 86 ms 19520 KB Output is correct
15 Correct 71 ms 20252 KB Output is correct