제출 #837400

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

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
using namespace std;
const int N = 200000+10, K = 20;

int n, dp[N][K], R[N], A[N], up[N][K];
vector<int> T[4*N];
void build(int l, int r, int k){
  if(l == r){
    T[k] = {R[l]};
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  merge(all(T[k<<1]), all(T[k<<1|1]), back_inserter(T[k]));
}

int get_max(int l, int r, int ql, int qr, int k, int X, int Y){
  if(ql > r || l > qr) return -1;
  if(ql <= l && r <= qr){
    int pos = upper_bound(all(T[k]), Y) - T[k].begin();
    if(pos > 0){
      int val = T[k][pos - 1];
      return (val >= X ? val : -1);
    }
    return -1;
  }
  int m = l+r>>1;
  return max(get_max(l, m, ql, qr, k<<1, X, Y), get_max(m+1, r, ql, qr, k<<1|1, X, Y));
}



int get(int l, int r){
  int k = int(log2(r-l+1));
  if(A[dp[l][k]] >= A[dp[r - (1<<k) + 1][k]])
    return dp[l][k];
  return dp[r - (1<<k) + 1][k];
}

void init(int _N, std::vector<int> H) {
  n = _N;
  for(int i = 1; i <= n; ++i) A[i] = H[i - 1];
  for(int i = 1; i <= n; ++i) dp[i][0] = i;
  for(int j = 1; j < K; ++j)
    for(int i = 1; i + (1<<j) <= n + 1; ++i){
      if(A[dp[i][j - 1]] >= A[dp[i+(1<<(j-1))][j - 1]])
        dp[i][j] = dp[i][j - 1];
      else
        dp[i][j] = dp[i+(1<<(j-1))][j - 1];
    }
  R[n] = n + 1;
  deque<int> q;
  q.pb(n);
  for(int i = n - 1; i >= 1; --i){
    while(!q.empty() && A[q.front()] <= A[i]) q.pop_front();
    if(q.empty()) R[i] = n + 1;
    else R[i] = q.front();
    q.push_front(i);
  }
  build(1, n, 1);
  R[n + 1] = n + 1;
  for(int i = 1; i <= n + 1; ++i) up[i][0] = R[i];
  for(int j = 1; j < K; ++j)
    for(int i = 1; i <= n + 1; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
}

int minimum_jumps(int A, int B, int C, int D) {
  A++, B++, C++, D++;
  int ans = mod, M = 0;
  if(B < C - 1){
    M = get(B+1, C-1);
    int v = M, co = 0, l = 1, r = n;
    while(l <= r){
    	int m = l+r>>1;
    	int u = M, coo = 0;
    	for(int j = K - 1; j >= 0; --j){
	      if(m & (1<<j))
	        u = up[u][j], coo += (1<<j);
	    }	
	    if(u >= C) co = coo, r = m - 1, v = u;
	    else l = m + 1; 
    }
    
    if(v >= C && v <= D){
      int p = get_max(1, n, A, B, 1, B+1, M);
      if(p != -1){
        co++;
        for(int j = K - 1; j >= 0; --j){
          if(up[p][j] <= M)
            p = up[p][j], co += (1<<j);
        }
        ans = co;
      }
    }
  }
  int p = get_max(1, n, A, B, 1, M + 1, D);
  if(p != -1){
  	int l = 0, r = n, co = mod, v = p;
	  while(l <= r){
    	int m = l+r>>1;
    	int u = p, coo = 0;
    	for(int j = K - 1; j >= 0; --j){
	      if(m & (1<<j))
	        u = up[u][j], coo += (1<<j);
	    }	
	    if(u >= C) co = coo, r = m - 1, v = u;
	    else l = m + 1; 
    }
    if(v >= C && v <= D)
	  	ans = min(ans, co + 1);
  }
  return (ans==mod?-1:ans);
}

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

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |   int m = l+r>>1;
      |           ~^~
jumps.cpp: In function 'int get_max(int, int, int, int, int, int, int)':
jumps.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = l+r>>1;
      |           ~^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |      int m = l+r>>1;
      |              ~^~
jumps.cpp:108:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |      int m = l+r>>1;
      |              ~^~

• Subtask 1: 4 / 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