제출 #860252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860252		mychecksedad	밀림 점프 (APIO21_jumps)	C++17	0 / 100	249 ms	142684 KiB

jumps

#include<jumps.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;

struct Node{
	Node *L, *R;
	int val = 0;
	Node(int v){
		L = R = nullptr;
		val = v;
	}
	Node(Node *l, Node *r){
		L = l, R = r;
		val = L->val + R->val;
	}
};

Node* build(int l, int r){
	if(l == r){
		return new Node(0);
	}
	int m = l+r>>1;
	return new Node(build(l, m), build(m+1, r));
}

Node* update(Node* v, int l, int r, int p){
	if(l == r){
		return new Node(1);
	}
	int m = l+r>>1;
	if(p <= m){
		return new Node(update(v->L, l, m, p), v->R);
	}
	return new Node(v->L, update(v->R, m+1, r, p));
}

int get(Node* vl, Node *vr, int l, int r, int lim){
	if(l == r)
		return (l < lim) > 0 ? l : -1;
	int m = l+r>>1;
	if(vr->R->val - vl->R->val > 0)
		return get(vl->R, vr->R, m+1, r, lim);
	return get(vl->L, vr->L, l, m, lim);
}


int n, L[N], R[N], up[N][K][2];
vector<int> H;
vector<Node*> roots;
void init(int _n, vector<int> h){
	n = _n;
	H = h;
	
	H.pb(MOD);

	deque<int> q;
	L[0] = n;
	q.pb(0);
	for(int i = 1; i < n; ++i){
		while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
		if(!q.empty()) L[i] = q.back();
		else L[i] = n;
		q.pb(i);
	}
	
	q.clear();
	R[n-1] = n;
	q.pb(n-1);
	for(int i = n-2; i >= 0; --i){
		while(!q.empty() && H[q.back()] < H[i]) q.pop_back();
		if(!q.empty()) R[i] = q.back();
		else R[i] = n;
		q.pb(i);
	}
	

	up[n][0][0] = n;
	up[n][0][1] = n;
	for(int i = 0; i < n; ++i){
		if(H[L[i]] > H[R[i]]){
			up[i][0][0] = L[i];
			up[i][0][1] = R[i];
		}else{
			up[i][0][1] = L[i];
			up[i][0][0] = R[i];
		}
	}
	for(int j = 1; j < K; ++j){
		for(int i = 0; i <= n; ++i){
			up[i][j][0] = up[up[i][j - 1][0]][j - 1][0];
			up[i][j][1] = up[up[i][j - 1][1]][j - 1][1];
		}
	}

	roots.pb(build(1, n));
	for(int i = 1; i <= n; ++i){
		roots.pb(update(roots.back(), 1, n, H[i - 1]));
	}
}
int minimum_jumps(int A, int B, int C, int D){
	int v, ans = 0;
	v = get(roots[B + 1], roots[A], 1, n, H[C]) - 1;

	if(v == -2) return -1;

	for(int j = K - 1; j >= 0; --j){
		if(H[up[v][j][0]] <= H[C]){
			ans += (1<<j);
			v = up[v][j][0];
		}
	}
	for(int j = K - 1; j >= 0; --j){
		if(H[up[v][j][1]] <= H[C]){
			ans += (1<<j);
			v = up[v][j][1];
		}
	}
	if(v == C) return ans;
	return -1;
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'Node* build(int, int)':
jumps.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int m = l+r>>1;
      |          ~^~
jumps.cpp: In function 'Node* update(Node*, int, int, int)':
jumps.cpp:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int m = l+r>>1;
      |          ~^~
jumps.cpp: In function 'int get(Node*, Node*, int, int, int)':
jumps.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |  int m = l+r>>1;
      |          ~^~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19