oj.uz

답안 #817852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817852 2023-08-09T18:04:21 Z YassirSalama Fountain (eJOI20_fountain) C++17
100 / 100
 338 ms 38616 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;
#pragma GCC ivdep
for(i=1;i<LOGN;i++){
  	#pragma GCC ivdep
    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:105:6: warning: unused variable 'nn' [-Wunused-variable]
  105 |  int nn=node;
      |      ^~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 32340 KB Output is correct
2 Correct 16 ms 32424 KB Output is correct
3 Correct 17 ms 32380 KB Output is correct
4 Correct 16 ms 32432 KB Output is correct
5 Correct 19 ms 32468 KB Output is correct
6 Correct 18 ms 32436 KB Output is correct
7 Correct 14 ms 32468 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 35580 KB Output is correct
2 Correct 210 ms 36436 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 32340 KB Output is correct
2 Correct 16 ms 32424 KB Output is correct
3 Correct 17 ms 32380 KB Output is correct
4 Correct 16 ms 32432 KB Output is correct
5 Correct 19 ms 32468 KB Output is correct
6 Correct 18 ms 32436 KB Output is correct
7 Correct 14 ms 32468 KB Output is correct
8 Correct 187 ms 35580 KB Output is correct
9 Correct 210 ms 36436 KB Output is correct
10 Correct 14 ms 32436 KB Output is correct
11 Correct 75 ms 35044 KB Output is correct
12 Correct 338 ms 36932 KB Output is correct
13 Correct 158 ms 36820 KB Output is correct
14 Correct 170 ms 36984 KB Output is correct
15 Correct 130 ms 38616 KB Output is correct