Submission #1342159

#TimeUsernameProblemLanguageResultExecution timeMemory
1342159bluocarootMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
248 ms217328 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3,inline")
using ll = long long;
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const long double pi = acos(-1), eps = 1e-4;
const int N = 3e5 + 10, K = 18 + 1, SQ = 320, M = 1e9 + 7;
const long long INF = 1e15;
//#define TESTS
//#define INTERACTIVE
//#define COMMUNICATION

/*
 * Remember who you are.
 */

void pre() {
}

struct Node {
    ll sum = 0, lazy = 0;
    Node *left = nullptr, *right = nullptr;
};

struct DST {
    int sz = 1;
    Node *root;

    DST(int n) {
        while (sz < n)
            sz <<= 1;
        root = new Node;
    }
    int get(Node *v)
    {
        if (v == nullptr)
            return 0;
        return v->sum;
    }
    void merge(Node *v) {
        v->sum = get(v->left) + get(v->right);
    }
    void prop(Node *v, int l, int r)
    {
        if (v->lazy)
        {
            v->sum = v->lazy * (r - l + 1);
            if (l != r)
            {
                if (v->left == nullptr)
                    v->left = new Node();
                v->left->lazy = v->lazy;
                if (v->right == nullptr)
                    v->right = new Node();
                v->right->lazy = v->lazy;
            }
            v->lazy = 0;
        }
    }
    ll query(Node *v, int l, int r, int ql, int qr) {
        if (v == nullptr)
            return 0;
        prop(v, l, r);
        if (ql > r || qr < l)
            return 0;
        if (ql <= l && r <= qr)
            return v->sum;
        int m = (l + r) / 2;
        return query(v->left, l, m, ql, qr) + query(v->right, m + 1, r, ql, qr);
    }

    void update(Node *v, int l, int r, int ql, int qr) {
        prop(v, l, r);
        if (ql > r || qr < l)
            return;
        if (v->sum == (r - l + 1)) return;
        if (ql <= l && r <= qr)
        {
            v->lazy = 1;
            prop(v, l, r);
            return;
        }
        int m = (l + r) / 2;

        if (ql <= m) {
            if (v->left == nullptr)
                v->left = new Node();
            update(v->left, l, m, ql, qr);
        }

        if (qr > m) {
            if (v->right == nullptr)
                v->right = new Node();
            update(v->right, m + 1, r, ql, qr);
        }
        merge(v);
    }


};

void solve() {
    int q;
    cin >> q;
    DST st(1e9 + 5);
    int c = 0;
    while (q--)
    {
        int t, l, r;
        cin >> t >> l >> r;
        l += c, r += c;
        if (t == 1)
            cout << (c = st.query(st.root, 0, st.sz - 1, l, r)) << '\n';
        else
        {
            st.update(st.root, 0, st.sz - 1, l, r);
        }
    }
}


void solve2() {

}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifdef CAROOT
    auto start = std::chrono::steady_clock::now();
#ifndef INTERACTIVE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
#else
#endif
    int tt = 1;
    pre();
#ifdef COMMUNICATION
    string run;
    cin >> run;
#endif
#ifdef TESTS
    cin >> tt;
#endif
    for (int tc = 1; tc <= tt; ++tc) {
#ifdef COMMUNICATION
        if (run == "first")
            solve();
        else
            solve2();
#else
        solve();
#endif
        cout << '\n';
    }
#ifdef CAROOT
    auto end = std::chrono::steady_clock::now();

    std::chrono::duration<double> elapsed_seconds = end - start;

    auto duration_ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    cerr << "Execution time: " << elapsed_seconds.count() << " seconds" << std::endl;
    cerr << "Execution time in milliseconds: " << duration_ms.count() << " ms" << std::endl;

#endif
}
#Verdict Execution timeMemoryGrader output
Fetching results...