oj.uz

답안 #979887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979887 2024-05-11T14:40:18 Z Malix 밀림 점프 (APIO21_jumps) C++14
0 / 100
 4000 ms 41196 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair

int INF=1e9+10;
vii R,L;

void init(int n, std::vector<int> a) {
  int m=log2(n);
  L.resize(n,vi(m+2,INF));
  R.resize(n,vi(m+2,INF));
  
  priority_queue<pi,vector<pi>,greater<pi>> pq;
  pq.push({a[0],0});
  REP(i,1,n){
    while(!pq.empty()&&pq.top().F<a[i]){
      R[pq.top().S][0]=i;
      pq.pop();
    }
    pq.push({a[i],i});
  }
  pq=priority_queue<pi,vector<pi>,greater<pi>>();
  pq.push({a[n-1],n-1});
  for(int i=n-2;i>=0;i--){
    while(!pq.empty()&&pq.top().F<a[i]){
      L[pq.top().S][0]=i;
      pq.pop();
    }
    pq.push({a[i],i});
  }
  //cout<<R[3][0];
  //REP(i,0,n){
    //cout<<L[i][0]<<" ";
    //cout<<R[i][0]<<" ";
    //cout<<"\n";
  //}
  REP(i,1,m+1){
    REP(j,0,n){
      if(L[j][i-1]!=INF)L[j][i]=min(L[j][i],L[L[j][i-1]][i-1]);
      if(R[j][i-1]!=INF)L[j][i]=min(L[j][i],L[R[j][i-1]][i-1]);
      if(L[j][i-1]!=INF)R[j][i]=max(L[j][i],R[L[j][i-1]][i-1]);
      if(R[j][i-1]!=INF)R[j][i]=max(L[j][i],R[R[j][i-1]][i-1]);
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  int ans=INF;
  REP(j,C,D+1)REP(i,A,B+1){
    //cout<<i<<"-";
    int c2=0;
    int it=lower_bound(R[i].begin(),R[i].end(),j)-R[i].begin();
    //cout<<R[A][it]<<it<<" "<<"\n";
    //cout<<R[3][0]<<"\n";
    if(j==R[i][it]){
      //cout<<it<<" ";
      ans=pow(2,it);
      continue;
    }
    if(it==0){
      c2=0;
      continue;
    }
    c2+=pow(2,it-1);
    int t=R[i][it-1];
    bool f=1;
    //cout<<"a";
    while(f){
      int it2=lower_bound(R[t].begin(),R[t].end(),j)-R[t].begin();
      //cout<<it2<<" ";
      if(j==R[t][it2]){
        c2+=pow(2,it2);
        f=0;
        break;
      }
      else{
        if(it2==0){
          c2=0;
          f=0;
          break;
        }
        c2+=pow(2,it2-1);
        t=R[t][it2-1];
      }
    }
    //cout<<"a";
    if(c2!=0)ans=min(c2,ans);
    //cout<<i<<" "<<ans<<"\n";
    //cout<<"\n";
  }
  //cout<<ans;
  if(ans==0||ans==INF)return -1;
  return ans;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4061 ms 41196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Execution timed out 4069 ms 39464 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4061 ms 41196 KB Time limit exceeded
4 Halted 0 ms 0 KB -