Submission #1312414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312414		chithanhnguyen	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	308 ms	205664 KiB

apple

/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

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

    int n;
    Node *root;

    SparseSegTree(int _n) : n(_n) {
        root = new Node;
    }

    void apply(Node *cur, int l, int r, int val) {
        if (val != 1) return;
        cur->sum = val * (r - l + 1);
        cur->lazy = val;
    }

    void push(Node *cur, int l, int r) {
        if(cur->left == nullptr) cur->left = new Node;
        if(cur->right == nullptr) cur->right = new Node;

        int mid = (l + r) >> 1;
        apply(cur->left, l, mid, cur->lazy);
        apply(cur->right, mid + 1, r, cur->lazy);
    }

    void update(Node *cur, int l, int r, int u, int v, int val) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            apply(cur, l, r, val);
            return;
        }

        push(cur, l, r);
        int mid = (l + r) >> 1;
        update(cur->left, l, mid, u, v, val);
        update(cur->right, mid + 1, r, u, v, val);

        cur->sum = cur->left->sum + cur->right->sum;
    }

    int get(Node *cur, int l, int r, int u, int v) {
        if (v < l || r < u) return 0;
        if (u <= l && r <= v) return cur->sum;

        push(cur, l, r);
        int mid = (l + r) >> 1;
        int get1 = get(cur->left, l, mid, u, v);
        int get2 = get(cur->right, mid + 1, r, u, v);

        return get1 + get2;
    }

    void update(int u, int v, int val) {update(root, 1, n, u, v, val);}
    int get(int u, int v) {return get(root, 1, n, u, v);}
};

void solve() {
    int m; cin >> m;
    SparseSegTree seg(1e9 + 7);

    int c = 0;
    while (m--) {
        int type, l, r; cin >> type >> l >> r;
        if (type == 1) {
            int res = seg.get(l + c, r + c);
            c = res;
            cout << res << '\n';
        } else {seg.update(l + c, r + c, 1);}
    }
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    solve();

    return 0;
}

• Subtask 1: 100 / 100