Submission #703703

#	Time	Username	Problem	Language	Result	Execution time	Memory
703703		Nursik	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	543 ms	48800 KiB

weirdtree

#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 (stderr)

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29