제출 #488867

#제출 시각아이디문제언어결과실행 시간메모리
488867cfalas밀림 점프 (APIO21_jumps)C++14
33 / 100
4064 ms30108 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 nodemax{ nodemax* L=NULL, *R=NULL; int val=-1; 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 nodemax(); if(!R) R = new nodemax(); val = -1; L->update(x, v, l, MID), val = max(val, L->val); R->update(x,v, MID+1,r), val = max(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 -1; else { if(!L) L = new nodemax(); if(!R) R = new nodemax(); return max(L->query(rl, rr, l, MID), R->query(rl,rr,MID+1,r)); } } }; 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; nodemax segm; void init(int N, std::vector<int> H) { n = N; a.resize(n); nl.resize(n); pl.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<<endl; pl[i] = segm.query(a[i], n-1); segm.update(a[i]-1, i); } //FOR(i,n) cout<<pl[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(nl[t]<n && !vis[nl[t]]){ vis[nl[t]] = true; q.push(nl[t]); } if(pl[t]>=0 && !vis[pl[t]]){ vis[pl[t]] = true; q.push(pl[t]); } } 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...