8326 | 2024. 01. 14 18:06:58 | TuruTamas | Bináris fa magassága (50 pont) | cpp17 | Elfogadva 50/50 | 20ms | 6072 KiB |
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
ifstream in_file("minta/be1.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef array<ll, 2> all;
struct segment {
ll len, val;
};
vector<segment> tree;
ll N, M, a, b;
void set_node(ll ind, ll val) {
tree[ind-1].len = val;
ll curr = ind/2;
while (curr > 0) {
tree[curr-1].val = max(
tree[curr*2-1].len + tree[curr*2-1].val,
tree[curr*2].len + tree[curr*2].val
);
curr /= 2;
}
}
int main() {
INTHENAMEOFGOD
input >> N >> M;
for (ll n = 0; n < N; n++) {
for (ll i = 0; i < 1 << n; i++) {
tree.push_back((segment) {
.len = 1,
.val = N-n-1,
});
}
}
for (ll m = 0; m < M; m++) {
input >> a >> b;
set_node(a, b);
cout << tree[0].val << "\n";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1888 KiB | |||
2 | Elfogadva | 0/0 | 19ms | 4392 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2408 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2548 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2764 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2728 KiB | |||
7 | Elfogadva | 3/3 | 3ms | 2872 KiB | |||
8 | Elfogadva | 3/3 | 3ms | 2800 KiB | |||
9 | Elfogadva | 3/3 | 3ms | 3080 KiB | |||
10 | Elfogadva | 3/3 | 3ms | 3164 KiB | |||
11 | Elfogadva | 2/2 | 19ms | 5248 KiB | |||
12 | Elfogadva | 2/2 | 19ms | 5308 KiB | |||
13 | Elfogadva | 2/2 | 19ms | 5528 KiB | |||
14 | Elfogadva | 2/2 | 19ms | 5388 KiB | |||
15 | Elfogadva | 2/2 | 19ms | 5520 KiB | |||
16 | Elfogadva | 2/2 | 18ms | 5528 KiB | |||
17 | Elfogadva | 2/2 | 18ms | 5524 KiB | |||
18 | Elfogadva | 2/2 | 19ms | 5516 KiB | |||
19 | Elfogadva | 2/2 | 18ms | 5644 KiB | |||
20 | Elfogadva | 3/3 | 19ms | 5732 KiB | |||
21 | Elfogadva | 3/3 | 20ms | 6072 KiB | |||
22 | Elfogadva | 3/3 | 19ms | 5940 KiB | |||
23 | Elfogadva | 3/3 | 19ms | 5944 KiB |