Submission #975058

#TimeUsernameProblemLanguageResultExecution timeMemory
975058yoav_sRainforest Jumps (APIO21_jumps)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef pair<ll, ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() const ll INF = 1e18; const ll mod = 1e9 + 7; #include "jumps.h" v H; ll N; v nextHigher; v height; v st; ll n; ll query(ll l, ll r) { l += n; r += n; ll res = -INF; while (l <= r) { if (l % 2 == 1) { res = max(res, st[l]); l++; } if (r % 2 == 0) { res = max(res,st[r]); r--; } l /= 2; r /= 2; } return res; } void init(int Nn, std::vector<int> Hh) { for (auto x : Hh) H.pb(x); N = Nn; nextHigher = v(N, N); stack<p> mon; for (ll i = N - 1; i >= 0; i--) { while (!mon.empty() && mon.top().s <= H[i]) mon.pop(); if (!mon.empty()) nextHigher[i] = mon.top().f; mon.emplace(i, H[i]); } vv reverseNextHigher(N + 1); for (ll i = 0; i < N; i++) reverseNextHigher[nextHigher[i]].pb(i); height = v(N + 1, -1); stack<p> dfs; dfs.emplace(N, 0); while (!dfs.empty()) { auto top = dfs.top(); dfs.pop(); assert(height[top.f] == -1); height[top.f] = top.s; for (ll x : reverseNextHigher[top.f]) dfs.emplace(x, top.s + 1); } n = pow(2, ceil(log2(N))); st = v(2 * n, -INF); for (ll i = 0; i < N; i++) st[n + i] = H[i]; for (ll i = n - 1; i> 0; i--) st[i] = max(st[2 * i], st[2 * i + 1]); } int minimum_jumps(int A, int B, int C, int D) { ll mini = INF; for (ll i = A; i <= B; i++) { for (ll j = C; j <= D; j++) { bool poss = query(i, j - 1) < H[j]; if (poss) mini = min(mini, abs(height[i] - height[j])); } } if (mini == INF) mini = -1; return mini; } int main() { int N, Q; assert(2 == scanf("%d %d", &N, &Q)); std::vector<int> H(N); for (int i = 0; i < N; ++i) { assert(1 == scanf("%d", &H[i])); } init(N, H); for (int i = 0; i < Q; ++i) { int A, B, C, D; assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D)); printf("%d\n", minimum_jumps(A, B, C, D)); } return 0; } /**/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccpTjoZA.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyvpxBE.o:jumps.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status