oj.uz

답안 #982926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982926 2024-05-15T04:16:21 Z shjeong 밀림 점프 (APIO21_jumps) C++17
4 / 100
 998 ms 115796 KB 
#include "jumps.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
ll n;
struct segtree{
    vector<ll> tree;
    segtree(): tree(808080){}
    void init(ll node, ll s, ll e, vector<ll> &v){
        if(s==e)tree[node] = v[s];
        else{
            ll mid = s+e>>1;
            init(node<<1,s,mid,v); init(node<<1|1,mid+1,e,v);
            tree[node] = max(tree[node<<1],tree[node<<1|1]);
        }
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(l>r)return -1;
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
    ll Q(ll l, ll r){ return query(1,1,n,l,r); }
} seg;
vector<ll> v;
ll L[202020][22];
ll R[202020][22];
ll M[202020][22];
void init(int N, std::vector<int> H) {
    n=N;
    v.push_back(0);
    for(int i = 1 ; i <= n ; i++)v.push_back(H[i-1]);
    seg.init(1,1,n,v);
    stack<ll> st;
    for(int i = 1 ; i <= n ; i++){
        while(st.size() and v[st.top()] < v[i]){
            R[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size())st.pop();
    for(int i = n ; i >= 1 ; i--){
        while(st.size() and v[st.top()] < v[i]){
            L[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }
    for(int i = 1 ; i <= n ; i++){
        M[i][0] = (v[L[i][0]] > v[R[i][0]] ? L[i][0] : R[i][0]);
    }
    for(int j = 1 ; j <= 20 ; j++){
        for(int i = 1 ; i <= n ; i++){
            L[i][j] = L[L[i][j-1]][j-1];
            R[i][j] = R[R[i][j-1]][j-1];
            M[i][j] = M[M[i][j-1]][j-1];
        }
    }
}
ll AB, BC, CD;
ll c;
int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    AB = seg.Q(A,B), BC = seg.Q(B+1,C-1), CD = seg.Q(C,D);
    if(BC>CD)return -1;
    ll ret = 0;
    ll cur = B;
    for(int i = 20 ; i >= 0 ; i--){
        if(L[cur][i]<=0)continue;
        if(L[cur][i]>=A and v[L[cur][i]] < CD)cur = L[cur][i];
    }
    for(int i = 20 ; i >= 0 ; i--){
        if(M[cur][i]<=0)continue;
        if(v[M[cur][i]]<CD and R[cur][i]>0 and R[cur][i]<C)cur = M[cur][i], ret += (1<<i);
    }
    ret++; cur = R[cur][0];
    if(cur<C or cur>D)ret = -1;
    return ret;
}
/*
10 100
8 7 2 1 3 4 5 6 9 10
3 3 9 9
 ans : 4
 */

Compilation message

jumps.cpp: In member function 'void segtree::init(ll, ll, ll, std::vector<long long int>&)':
jumps.cpp:26:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |             ll mid = s+e>>1;
      |                      ~^~
jumps.cpp: In member function 'll segtree::query(ll, ll, ll, ll, ll)':
jumps.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         ll mid = s+e>>1;
      |                  ~^~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 185 ms 97800 KB Output is correct
4 Correct 998 ms 115568 KB Output is correct
5 Correct 789 ms 65484 KB Output is correct
6 Correct 984 ms 115796 KB Output is correct
7 Correct 743 ms 84936 KB Output is correct
8 Correct 972 ms 115580 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8824 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Incorrect 3 ms 10840 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8824 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Incorrect 3 ms 10840 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 103 ms 99852 KB Output is correct
6 Correct 110 ms 114048 KB Output is correct
7 Correct 58 ms 68156 KB Output is correct
8 Correct 116 ms 114048 KB Output is correct
9 Correct 13 ms 29908 KB Output is correct
10 Correct 115 ms 113900 KB Output is correct
11 Correct 128 ms 115444 KB Output is correct
12 Incorrect 122 ms 115148 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Incorrect 200 ms 61784 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Incorrect 200 ms 61784 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 185 ms 97800 KB Output is correct
4 Correct 998 ms 115568 KB Output is correct
5 Correct 789 ms 65484 KB Output is correct
6 Correct 984 ms 115796 KB Output is correct
7 Correct 743 ms 84936 KB Output is correct
8 Correct 972 ms 115580 KB Output is correct
9 Correct 2 ms 10836 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8824 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Incorrect 3 ms 10840 KB Output isn't correct
14 Halted 0 ms 0 KB -