oj.uz

Submission #703703

# Submission time Handle Problem Language Result Execution time Memory
703703 2023-02-28T07:09:13 Z Nursik Weirdtree (RMI21_weirdtree) C++14
100 / 100
 543 ms 48800 KB 
#include "weirdtree.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
 #include <cstdint>
#include <cassert>
#include <functional>
#include <complex>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

const int maxn = 3e5 + 200, maxm = 1e4 + 200, inf = 1e9;

int n;
struct node{
    ll sum = 0;
    ll max1 = 0;
    ll max2 = 0;
    ll fr = 0;
} t[maxn * 4];

ll mv[maxn * 4];
node merge(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    c.max1 = max(a.max1, b.max1);
    if (a.max1 == b.max1){
        c.fr = a.fr + b.fr;
        c.max2 = max(a.max2, b.max2);
    }
    else{
        if (a.max1 > b.max1){
            c.fr = a.fr;
            c.max2 = max(a.max2, b.max1);
        }
        else{
            c.fr = b.fr;
            c.max2 = max(b.max2, a.max1);
        }
    }
    return c;
}
void push(int v, int l, int r){
    if (mv[v]){
        if (l != r){
            if (t[v + v].max1 + mv[v + v] == t[v].max1){
                mv[v + v] += mv[v];
            }
            if (t[v + v + 1].max1 + mv[v + v + 1] == t[v].max1){
                mv[v + v + 1] += mv[v];
            }
        }
        t[v].sum += mv[v] * t[v].fr;
        t[v].max1 += mv[v];
        mv[v] = 0;
    }
}
void upd(int pos, ll val, int v = 1, int tl = 1, int tr = n){
    push(v, tl, tr);
    if (tl == tr){
        t[v].sum = val;
        t[v].max1 = val;
        t[v].fr = 1;
        t[v].max2 = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm){
        upd(pos, val, v + v, tl, tm);
    }
    else{
        upd(pos, val, v + v + 1, tm + 1, tr);
    }
    push(v + v, tl, tm);
    push(v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
}
node get(int l, int r, int v = 1, int tl = 1, int tr = n){
    push(v, tl, tr);
    if (l <= tl && tr <= r){
        return t[v];
    }
    if (l > tr || r < tl){
        node cl;
        cl.sum = 0;
        cl.max1 = 0;
        cl.max2 = 0;
        cl.fr = 0;
        return cl;
    }
    int tm = (tl + tr) / 2;
    return merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
void updlr(int l, int r, ll x, ll mx, int v = 1, int tl = 1, int tr = n){
    push(v, tl, tr);
    if (l > tr || r < tl || t[v].max1 < mx)
        return;
    if (l <= tl && tr <= r && t[v].max1 - x > t[v].max2 && t[v].max1 == mx){
        mv[v] -= x;
        push(v, tl, tr);
        return;
    }
    if (tl == tr && t[v].max1 == mx){
        mv[v] -= (x);
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    updlr(l, r, x, mx, v + v, tl, tm);
    updlr(l, r, x, mx, v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
}
void updlr2(int l, int r, ll x, ll &y, ll mx, int v = 1, int tl = 1, int tr = n){
    push(v, tl, tr);
    if (l > tr || r < tl || t[v].max1 < mx){
        return;
    }
    if (l <= tl && tr <= r && t[v].max1 - x - (y > 0) > t[v].max2 && (y == 0 || y >= t[v].fr) && t[v].max1 == mx){
        mv[v] -= (x + (y > 0));
        y = max(0ll, y - t[v].fr);
        push(v, tl, tr);
      //  cout << t[v].sum << '\n';
      //  cout << mv[v + v] << " " << mv[v + v + 1] << '\n';
       // cout << "kekok\n";
        return;
    }
    if (tl == tr && t[v].max1 == mx && (y == 0 || y >= t[v].fr)){
        mv[v] -= (x + (y > 0));
        y = max(0ll, y - t[v].fr);
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    updlr2(l, r, x, y, mx, v + v, tl, tm);
    updlr2(l, r, x, y, mx, v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
}
ll gets(int l, int r, int v = 1, int tl = 1, int tr = n){
    push(v, tl, tr);
    if (l <= tl && tr <= r)
        return t[v].sum;
    if (l > tr || r < tl)
        return 0;
    int tm = (tl + tr) / 2;
    return gets(l, r, v + v, tl, tm) + gets(l, r, v + v + 1, tm + 1, tr);
}
void initialise(int N, int Q, int h[]) {
    n = N;
    for (int i = 1; i <= n; ++i){
        upd(i, h[i]);
    }
}
void cut(int l, int r, int k) {
    while (k > 0){
        node cur = get(l, r);
        if (cur.max1 == 0){
            break;
        }
        ll rz = cur.max1 - cur.max2;
        if (rz * cur.fr <= k){
            updlr(l, r, rz, cur.max1);
            k -= rz * cur.fr;
        }
        else{
            ll all = rz * cur.fr;
            ll is = k % cur.fr;
          //  cout << "ok\n";
            updlr2(l, r, k / cur.fr, is, cur.max1); 
            k = 0;
            break;
        }
    }
}
void magic(int i, int x) {
    upd(i, x);
}
long long int inspect(int l, int r) {
	// Your code here.
    return gets(l, r);
}

Compilation message

weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:193:16: warning: unused variable 'all' [-Wunused-variable]
  193 |             ll all = rz * cur.fr;
      |                ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 92 ms 12596 KB Output is correct
4 Correct 121 ms 12504 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 543 ms 48796 KB Output is correct
4 Correct 463 ms 48800 KB Output is correct
5 Correct 489 ms 48596 KB Output is correct
6 Correct 454 ms 48248 KB Output is correct
7 Correct 38 ms 10952 KB Output is correct
8 Correct 72 ms 12700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10952 KB Output is correct
2 Correct 72 ms 12700 KB Output is correct
3 Correct 224 ms 36676 KB Output is correct
4 Correct 258 ms 45016 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 92 ms 12596 KB Output is correct
4 Correct 121 ms 12504 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 38 ms 10952 KB Output is correct
8 Correct 72 ms 12700 KB Output is correct
9 Correct 87 ms 12504 KB Output is correct
10 Correct 93 ms 12492 KB Output is correct
11 Correct 92 ms 12492 KB Output is correct
12 Correct 98 ms 12644 KB Output is correct
13 Correct 91 ms 12668 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 92 ms 12596 KB Output is correct
4 Correct 121 ms 12504 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 543 ms 48796 KB Output is correct
8 Correct 463 ms 48800 KB Output is correct
9 Correct 489 ms 48596 KB Output is correct
10 Correct 454 ms 48248 KB Output is correct
11 Correct 224 ms 36676 KB Output is correct
12 Correct 258 ms 45016 KB Output is correct
13 Correct 87 ms 12504 KB Output is correct
14 Correct 93 ms 12492 KB Output is correct
15 Correct 92 ms 12492 KB Output is correct
16 Correct 98 ms 12644 KB Output is correct
17 Correct 91 ms 12668 KB Output is correct
18 Correct 38 ms 10952 KB Output is correct
19 Correct 72 ms 12700 KB Output is correct
20 Correct 417 ms 47280 KB Output is correct
21 Correct 437 ms 48164 KB Output is correct
22 Correct 414 ms 47768 KB Output is correct
23 Correct 436 ms 47948 KB Output is correct
24 Correct 404 ms 47812 KB Output is correct