Submission #485732

#	Time	Username	Problem	Language	Result	Execution time	Memory
485732		wwdd	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1099 ms	15280 KiB

jumps

#include "jumps.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
class ST {
	private:
		vi st;
		vi wo;
		int n;
	public:
		ST() {}
		ST(vi wals) {
			n = wals.size();
			st.assign(2*n,0);
			wo = wals;
			for(int i=0;i<n;i++) {
				st[i+n] = i;
			}
			for(int i=n-1;i>0;i--) {
				int ia = st[i<<1];
				int ib = st[i<<1|1];
				st[i] = (wo[ia]>wo[ib]?ia:ib);
			}
		}
		int get(int l, int r) {
			int res = l;
			l += n;r += n;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {
					int idx = st[l];
					if(wo[idx] > wo[res]) {
						res = idx;
					}
					l++;
				}
				if(r&1) {
					--r;
					int idx = st[r];
					if(wo[idx] > wo[res]) {
						res = idx;
					}
				}
			}
			return res;
		}
};

class U {
	private:
		vi rk,p,mu,sz;
		int n;
	public:
		U(int n_) {
			n = n_;
			rk.assign(n,0);
			for(int i=0;i<n;i++) {
				p.push_back(i);
				mu.push_back(i);
			}
			sz.assign(n,1);
		}
		int find(int a) {
			if(p[a] == a) {return a;}
			return p[a] = find(p[a]);
		}
		bool same(int a, int b) {
			return find(a) == find(b);
		}
		bool un(int a, int b) {
			if(same(a,b)) {return false;}
			int x = find(a),y = find(b);
			int so = mu[x];
			if(rk[y] > rk[x]) {
				swap(x,y);
			}
			if(rk[x] == rk[y]) {rk[x]++;}
			p[y] = x;
			mu[x] = so;
			sz[x] += sz[y];
			return true;
		}
		int rep(int a) {
			return mu[find(a)];
		}
		int num(int a) {
			return sz[find(a)];
		}
};
typedef pair<int,int> ii;
vi lev;
vi pa,jo;
vi lpa,ljo,lde;
vector<ii> wseg;
ST st;
void init(int N, std::vector<int> H) {
	lev.assign(N+1,0);
	pa.assign(N+1,N);
	jo.assign(N+1,N);
	wseg.resize(N+1);
	vi ord(N);
	st = ST(H);
	for(int i=0;i<H.size();i++) {
		H[i]--;
		ord[H[i]] = i;
	}
	U bu(N+1);
	for(int i=0;i<ord.size();i++) {
		int u = ord[i];
		int lf = u;
		int rt = u;
		if(u > 0) {
			int v = bu.rep(u-1);
			if(H[v] < H[u]) {
				pa[v] = u;
				lf -= bu.num(v);
				bu.un(u,v);
			}
		}
		if(u < N-1) {
			int v = bu.rep(u+1);
			if(H[v] < H[u]) {
				pa[v] = u;
				rt += bu.num(v);
				bu.un(u,v);
			}
		}
		wseg[u] = {lf,rt};
	}
	int ro = bu.rep(0);
	lpa.assign(N+1,N);
	lde.assign(N+1,0);
	ljo.assign(N+1,N);
	stack<int> so;
	for(int i=0;i<N;i++) {
		while(!so.empty() && H[so.top()] < H[i]) {
			int u = so.top();so.pop();
			if(i != pa[u]) {
				lpa[u] = i;
			}
		}
		so.push(i);
	}
	so = stack<int>();
	for(int i=N-1;i>=0;i--) {
		while(!so.empty() && H[so.top()] < H[i]) {
			int u = so.top();so.pop();
			if(i != pa[u]) {
				lpa[u] = i;
			}
		}
		so.push(i);
	}
	for(int i=ord.size()-1;i>=0;i--) {
		int u = ord[i];
		lev[u] = lev[pa[u]]+1;
		lde[u] = lde[lpa[u]]+1;
		{
			int p = pa[u];
			if(lev[p]-lev[jo[p]] == lev[jo[p]]-lev[jo[jo[p]]]) {
				jo[u] = jo[jo[p]];
			} else {
				jo[u] = p;
			}
		}
		{
			int p = lpa[u];
			if(lde[p] - lde[ljo[p]] == lde[ljo[p]] - lde[ljo[ljo[p]]]) {
				ljo[u] = ljo[ljo[p]];
			} else {
				ljo[u] = p;
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	int N = lev.size()-1;
	int hr = st.get(C,D+1);
	int sv;
	{
		ii se = wseg[hr];
		if(se.first > B) {return -1;}
		se.first = max(se.first,A);
		se.second = min(se.second,B);
		sv = st.get(se.first,se.second+1);
	}
	int ans = 0;
	int rv = sv;
	while(1) {
		int jv = ljo[rv];
		int pv = lpa[rv];
		if(jv < N && wseg[jv].second < C) {
			rv = jv;
		} else if(pv < N && wseg[pv].second < C) {
			rv = pv;
		} else {
			ans += lde[sv]-lde[rv];
			break;
		}
	}
	{
		int ok = rv;
		int ad = N+1;
		int ba = lpa[rv];
		if(C <= ba && ba <= D) {
			ad = min(ad,1);
		} else if(ba < N && wseg[ba].second < D) {
			ad = min(ad,2);
		}
		{
			while(1) {
				if(lev[ok]-lev[rv] >= ad) {break;}
				int jv = jo[rv];
				int pv = pa[rv];
				if(jv < N && wseg[jv].second < C) {
					rv = jv;
				} else if(pv < N && wseg[pv].second < C) {
					rv = pv;
				} else {
					rv = pa[rv];
					if(C <= rv && rv <= D) {
						ad = min(ad,lev[ok]-lev[rv]);
					} else {
						ad = min(ad,lev[ok]-lev[rv]+1);
					}
					break;
				}
			}
		}
		ans += ad;
	}
	return ans;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i=0;i<H.size();i++) {
      |              ~^~~~~~~~~
jumps.cpp:111:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i=0;i<ord.size();i++) {
      |              ~^~~~~~~~~~~
jumps.cpp:133:6: warning: unused variable 'ro' [-Wunused-variable]
  133 |  int ro = bu.rep(0);
      |      ^~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19