제출 #1198333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198333		Tymond	Weirdtree (RMI21_weirdtree)	C++20	100 / 100	573 ms	43680 KiB

weirdtree

#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

struct Node{
    ll mx1, mx2, f1, sum;
    Node(){
        mx1 = mx2 = f1 = sum = 0LL;
    }
    Node(ll a){
        mx1 = sum = a;
        f1 = 1LL;
        mx2 = 0LL;
    }
    Node(ll a, ll b, ll c, ll d){
        mx1 = a;
        mx2 = b;
        f1 = c;
        sum = d;
    }

    Node operator+(const Node& other) const{
        if(mx1 == other.mx1){
            return Node(mx1, max(mx2, other.mx2), f1 + other.f1, sum + other.sum);
        }else if(mx1 > other.mx1){
            return Node(mx1, max(mx2, other.mx1), f1, sum + other.sum);
        }else{
            return Node(other.mx1, max(mx1, other.mx2), other.f1, sum + other.sum);
        }
    }
};

const int BASE = (1 << 19);
Node tree[2 * BASE + 7];
ll lazy[2 * BASE + 7];
ll H[BASE];
int n, q;

void Push(int v){
    ll xdd = max(tree[2 * v].mx1, tree[2 * v + 1].mx1);
    if(tree[2 * v].mx1 == xdd){
        tree[2 * v].mx1 -= lazy[v];
        tree[2 * v].sum -= (lazy[v] * tree[2 * v].f1);
        lazy[2 * v] += lazy[v];
    }

    if(tree[2 * v + 1].mx1 == xdd){
        tree[2 * v + 1].mx1 -= lazy[v];
        tree[2 * v + 1].sum -= (lazy[v] * tree[2 * v + 1].f1);
        lazy[2 * v + 1] += lazy[v];
    }
    lazy[v] = 0LL;
}

void upd(int v, int l, int p, int i, ll x){
    if(l == p){
        tree[v].sum = x;
        tree[v].mx1 = x;
        lazy[v] = 0LL;
        return;
    }
    Push(v);
    int mid = (l + p) / 2;
    if(i <= mid){
        upd(2 * v, l, mid, i, x);
    }else{
        upd(2 * v + 1, mid + 1, p, i, x);
    }
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

ll query(int v, int l, int p, int a, int b){
    if(p < a || b < l){
        return 0LL;
    }

    if(a <= l && p <= b){
        return tree[v].sum;
    }
    Push(v);
    int mid = (l + p) / 2;
    ll ret = (ll)query(2 * v, l, mid, a, b) + query(2 * v + 1, mid + 1, p, a, b);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
    return ret;
}

void initialise(int N, int Q, int h[]) {
    n = N;
    q = Q;
    for(int i = 1; i <= n; i++){
        H[i] = h[i];
        tree[i + BASE] = Node(H[i]);
    }

    for(int i = BASE; i >= 1; i--){
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
}

Node join(int v, int l, int p, int a, int b){
    if(p < a || b < l){
        return Node();
    }

    if(a <= l && p <= b){
        return tree[v];
    }
    Push(v);
    int mid = (l + p) / 2;
    Node ret = join(2 * v, l, mid, a, b) + join(2 * v + 1, mid + 1, p, a, b);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
    return ret;
}

ll v1,c1, v2, c2,mx1,mx2;
void changeAll(int v, int l, int p, int a, int b){
    if(p < a || b < l){
        return;
    }

    if(a <= l && p <= b){
        if(tree[v].mx1 < mx1){
            return;
        }
        if(l == p){
            tree[v].mx1 = mx2;
            tree[v].sum -= (tree[v].f1 * (mx1 - mx2));
            return;
        }
    }
    Push(v);
    int mid = (l + p) / 2;
    changeAll(2 * v, l, mid ,a, b);
    changeAll(2 * v + 1, mid + 1, p, a, b);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

pll used = mp(0LL, 0LL);
void change(int v, int l, int p, int a, int b){
    if(p < a || b < l){
        return;
    }

    if(a <= l && p <= b){
        if(tree[v].mx1 < mx1){
            return;
        }

        if(used.fi + tree[v].f1 <= c1){
            tree[v].mx1 = v1;
            used.fi += tree[v].f1;
            tree[v].sum -= (tree[v].f1 * (mx1 - v1));
            lazy[v] += (mx1 - v1);
            return;
        }else if(used.fi == c1){
            tree[v].mx1 = v2;
            used.se += tree[v].f1;
            tree[v].sum -= (tree[v].f1 * (mx1 - v2));
            lazy[v] += (mx1 - v2);
            return;
        }
    }
    //cerr << used << ' ' << c1 << ' ' << c2 << ' ' << tree[v].f1 << '\n';
    Push(v);
    int mid = (l + p) / 2;
    change(2 * v, l, mid, a, b);
    change(2 * v + 1, mid + 1, p, a, b);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

void cut(int l, int r, int k) {
    //cout << "-----\n";
    while(k){
        Node curr = join(1, 0, BASE - 1, l, r);
        /*for(int i = 1; i <= 6; i++){
            cout << tree[i + BASE].mx1 << ' ';
        }
        cout << '\n';
        cout << curr.mx1 << ' ' << curr.mx2 << ' ' << curr.f1 << '\n';
        cout << (ll)(curr.mx1 - curr.mx2) * curr.f1 << ' ' << k << '\n';
        cerr << "XD\n";*/
        mx1 = curr.mx1;
        mx2 = curr.mx2;
        if((ll)(curr.mx1 - curr.mx2) * curr.f1 > k){
            v1 = (k + curr.f1 - 1) / curr.f1;
            v2 = k / curr.f1;
            c1 = k - curr.f1 * v2;
            c2 = curr.f1 - c1;
            v1 = mx1 - v1;
            v2 = mx1 - v2;

            used = mp(0, 0);
            change(1, 0, BASE - 1, l, r);
            k = 0;
        }else{
            k = (ll)k - (ll)(curr.mx1 - curr.mx2) * curr.f1;
            changeAll(1, 0, BASE - 1, l, r);
            if(curr.mx2 == 0){
                k = 0;
            }
        }
    }
}

void magic(int i, int x){
    H[i] = x;
    upd(1, 0, BASE - 1, i, x);
}

ll inspect(int l, int r) {
    return query(1, 0, BASE - 1, l, r);
}

/*int main(){
    int h[7] = {0, 1, 2, 3, 1, 2, 3};
    initialise(6, 10, h);
    cut(1, 6, 3);
    //for(int i = 1; i <= 6; i++){
    //    cout << tree[i + BASE].mx1 << ' ';
    //}
    //cout << '\n';
    cout << inspect(1, 6) << '\n';
    cut(1, 3, 3);
    cout << inspect(1, 6) << '\n';
    cut(1, 3, 1000);
    cout << inspect(1, 6) << '\n';
    magic(1, 1000);
    cout << inspect(1, 6) << '\n';
    cut(1, 3, 999);
    cout << inspect(1, 5) << '\n';
    return 0;
}*/

• 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