oj.uz

Submission #983372

# Submission time Handle Problem Language Result Execution time Memory
983372 2024-05-15T11:35:17 Z hocln Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 33984 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
//const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
constexpr int N = 2e5 + 15;
constexpr int LOG = 20;
int nxt[N][LOG], be[N][LOG];
void init(int n, vector<int>h) {
	stack<int>st;
	for(int i = 0;i < LOG;i++) nxt[n-1][i] = n - 1,be[0][i]=0;
	st.push(n-1);
	for(int i = n - 2;i >= 0;i--) {
		while(!st.empty() && h[st.top()] <= h[i]) st.pop();
		int nx = (st.empty() ? i : st.top());
		//debug()<<imie(i)imie(nx);
		nxt[i][0] = nx;
		for(int j = 1;j < LOG;j++) nxt[i][j] = nxt[nxt[i][j-1]][j-1];
		st.push(i);
	}
	while(!st.empty()) st.pop();
	st.push(0);
	for(int i = 1;i < n;i++) {
		while(!st.empty() && h[st.top()] <= h[i]) st.pop();
		int b = (st.empty() ? i : st.top());
		//debug()<<imie(i)imie(b);
		be[i][0] = b;
		for(int j = 1;j < LOG;j++) be[i][j] = be[be[i][j-1]][j-1];
		st.push(i);
	}
}

int minimum_jumps(int a, int b, int c, int d) {
	int ans = inf;
	for(int j = a;j <= b;j++) {
		int cur = j, amt = 0;
		for(int k = 0;k < 20;k++) {
			if(nxt[cur][k] == cur) break;
			if(nxt[cur][k] > d) {
				if(k == 0) break;
				cur = nxt[cur][k-1];
				amt += 1 << (k - 1);
				k = -1;
			}
			else if(nxt[cur][k] >= c && nxt[cur][k] <= d) {
				chmin(ans, amt + (1 << k));
				break;
			}
		}
	}
	//for(int j = c;j <= d;j++) {
		//int cur = j, amt = 0;
		//for(int k = 0;k < 20;k++) {
			//if(be[cur][k] == cur) break;
			//if(be[cur][k] < a) {
				//if(k == 0) break;
				//cur = be[cur][k-1];
				//amt += 1 << (k - 1);
				//k = -1;
			//}
			//else if(be[cur][k] >= a && be[cur][k] <= b) {
				//chmin(ans,amt + (1 << k));
				//break;
			//}
		//}
	//}
	return (ans == inf ? -1 : ans);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Execution timed out 4027 ms 28976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 41 ms 30648 KB Output is correct
6 Correct 52 ms 33376 KB Output is correct
7 Correct 32 ms 19796 KB Output is correct
8 Correct 52 ms 33240 KB Output is correct
9 Correct 10 ms 9056 KB Output is correct
10 Correct 51 ms 33100 KB Output is correct
11 Incorrect 63 ms 33984 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 164 ms 19764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 164 ms 19764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Execution timed out 4027 ms 28976 KB Time limit exceeded
4 Halted 0 ms 0 KB -