Submission #526324

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
526324	2022-02-14 10:30:20	Vladithur	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	3170 ms	40980 KiB

jumps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200001, logn = 20;
int t[maxn * 4], t2[maxn * 4], up[maxn][logn], up2[maxn][logn];
vector<int> h;
void update(int v, int tl, int tr, int i, int x) {
  if (tl == tr - 1) {
    t[v] = x;
    t2[v] = tl;
  } else {
    int tm = (tl + tr) / 2;
    if (i < tm) update(2*v + 1, tl, tm, i, x);
    else update(2*v + 2, tm, tr, i, x);
    t[v] = max(t[2*v + 1], t[2*v + 2]);
    if (t[2*v + 1] > t[2*v + 2]) t2[v] = t2[2*v + 1];
    else t2[v] = t2[2*v + 2];
  }
}
pair<int, int> query(int v, int tl, int tr, int l, int r) {
  if (l >= r) return {0, 0};
  else if (tl == l && tr == r) return {t[v], t2[v]};
  else {
    int tm = (tl + tr) / 2;
    auto r1 = query(2*v + 1, tl, tm, l, min(r, tm));
    return max(r1, query(2*v + 2, tm, tr, max(l, tm), r));
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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