제출 #488864

#제출 시각아이디문제언어결과실행 시간메모리
488864cfalas밀림 점프 (APIO21_jumps)C++14
21 / 100
4067 ms16640 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) int t, n; vi a, b; vi nl, pl; struct node{ node* L=NULL, *R=NULL; int val=n; void update(int x, int v, int l=0, int r=n-1){ if(l==r && l==x){ val = v; //cout<<l<<" "<<r<<" "<<val<<endl; } else if(l==r || l>x || r<x) return; else{ if(!L) L = new node(); if(!R) R = new node(); val = n; L->update(x, v, l, MID), val = min(val, L->val); R->update(x,v, MID+1,r), val = min(val, R->val); //cout<<l<<" "<<r<<" "<<val<<endl; } } int query(int rl, int rr, int l=0, int r=n-1){ if(rl<=l && r<=rr) return val; else if(rl>r || l>rr) return n; else { if(!L) L = new node(); if(!R) R = new node(); return min(L->query(rl, rr, l, MID), R->query(rl,rr,MID+1,r)); } } }; node seg; void init(int N, std::vector<int> H) { n = N; a.resize(n); nl.resize(n); FOR(i,n) a[i] = H[i]; FORi(i,1,n+1){ //cout<<endl; nl[n-i] = seg.query(a[n-i], n-1); seg.update(a[n-i]-1, n-i); } //FOR(i,n) cout<<nl[i]<<" "; //cout<<endl; } int minimum_jumps(int A, int B, int C, int D) { queue<int> q; vi vis(n+1, false); FORi(i,A,B+1) q.push(i), vis[i] = true; q.push(-1); int ans=0; bool f = false; while(q.size()>1){ int t = q.front(); q.pop(); if(t==-1){ ans++; q.push(-1); continue; } if(C<=t && t<=D){ f = true; break; } if(!vis[nl[t]] && nl[t]<n){ vis[nl[t]] = true; q.push(nl[t]); } FORi(i,1,t+1){ if(!vis[t-i] && a[t-i]>a[t]){ vis[t-i] = true; q.push(t-i); break; } else if(a[t-i]>a[t]) break; } } if(f) return ans; else return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...