Submission #975150

#TimeUsernameProblemLanguageResultExecution timeMemory
975150yoav_sRainforest Jumps (APIO21_jumps)C++17
4 / 100
601 ms2160 KiB
#include <bits/stdc++.h> using namespace std; typedef int 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 prevHigher; v st; ll n; vv largestLifting; v rightHeight; ll logN; v nextLargest; vv nextLifting; ll query(ll l, ll r, v &st, bool maxi = true) { ll n = st.size() / 2; l += n; r += n; ll res = maxi? -INF : INF; while (l <= r) { if (l % 2 == 1) { if (maxi) res = max(res, st[l]); else res = min(res, st[l]); l++; } if (r % 2 == 0) { if (maxi) res = max(res,st[r]); else res = min(res, st[l]); r--; } l /= 2; r /= 2; } return res; } ll largestSmaller(ll l, ll r, ll threshold, v &st) { ll n = st.size() / 2; l += n; r += n; v segs, segsRev; while (l <= r) { if (l % 2 == 1) { segs.pb(l); l++; } if (r % 2 == 0) { segsRev.pb(r); r--; } l /= 2; r /= 2; } reverse(all(segs)); for (ll x : segs) segsRev.pb(x); v relevantSegs; ll lastSeg = -1; for (ll x : segsRev) { if (st[x] >= threshold) { lastSeg = x; break; } relevantSegs.pb(x); } ll lastSegMaxi = -INF; if (lastSeg != -1) { ll cur = lastSeg; while (cur < n) { if (st[2 * cur + 1] < threshold) { lastSegMaxi = max(lastSegMaxi, st[2 * cur + 1]); cur *= 2; } else cur = 2 * cur + 1; } } ll best = -INF; for (ll x : relevantSegs) best = max(best, st[x]); if (best > lastSegMaxi) { for (ll x : relevantSegs) { if (st[x] == best) { ll cur = x; while (cur < n) { if (st[2 * cur] == best) cur *= 2; else cur = 2 * cur + 1; } return cur - n; } } } if (lastSegMaxi == -INF) return -1; ll cur = lastSeg; while (cur < n) { if (st[2 * cur + 1] >= lastSegMaxi) cur = 2 * cur + 1; else cur *= 2; } return cur - n; } void init(int Nn, std::vector<int> Hh) { } int minimum_jumps(int A, int B, int C, int D) { return C - B; } /* 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)

jumps.cpp:171:1: warning: "/*" within comment [-Wcomment]
  171 | /**/
      |  
jumps.cpp:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~
#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...