Submission #1273654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273654		amigoo99234	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	437 ms	253540 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1e9 + 7;
//long long MOD = 7340033;
//const long long MOD = 998244353;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define popCnt(x) (__builtin_popcountll(x))
#define int long long

#define F  first
#define S  second
//#define double long double
#define pi  M_PI
#define all(x) x.begin() , x.end()
#define ll long long

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = 1e9, N = 2e9 , LOG = 27;


struct Node {
    Node *l = nullptr, *r = nullptr;
    ll sum = 0, lazy = -1;

    Node(ll s = 0, Node *l = NULL, Node *r = NULL) :
            sum(s), l(l), r(r), lazy(-1) {}
};

ll getS(Node *x) { return x == NULL ? 0 : x->sum; }


void pushDown(Node *&node, int l, int r) {
    if (!node || node->lazy == -1 || l == r)return;

    if (!node->l) node->l = new Node();
    if (!node->r) node->r = new Node();

    int mid = (l + r) >> 1;
    int val = node->lazy;

    node->l->lazy = val;
    node->r->lazy = val;
    node->l->sum = (mid - l + 1) * val;
    node->r->sum = (r - mid) * val;
    node->lazy = -1;
}

void upd(int ql, int qr, int val, Node *&x, int l = 1, int r = N) {
    if (!x) x = new Node();
    if (qr < l || ql > r)return;
    if (l >= ql && r <= qr) {
        x->sum = val * (r - l + 1);
        x->lazy = val;
        return;
    }

    pushDown(x, l, r);


    int mid = (l + r) >> 1;

    upd(ql, qr, val, x->l, l, mid);
    upd(ql, qr, val, x->r, mid + 1, r);
    x->sum = getS(x->l) + getS(x->r);

}

ll qry(int l, int r, Node *x, int nl = 1, int nr = N) {
    if (!x)return 0;
    if (nr < l || nl > r)return 0;
    pushDown(x, nl, nr);

    if (nl >= l && nr <= r) {
        return x->sum;
    }


    int mid = (nl + nr) >> 1;
    return qry(l, r, x->l, nl, mid) + qry(l, r, x->r, mid + 1, nr);
}

signed main() {
    fast;


    int t = 1;
//    cin >> t;
    for (int tct = 1; tct <= t; tct++) {
        int q;
        cin >> q;

        Node *root = NULL;

        int c = 0;
        while (q--) {
            int d, l, r;
            cin >> d >> l >> r;
            ll L = l + c;
            ll R = r + c;
            if (d == 1) {
                ll ans = qry((int)L, (int)R, root);
                cout << ans << '\n';
                c = (int)ans;
            } else {
                upd((int)L, (int)R, 1, root);
            }
        }
    }
}

• Subtask 1: 100 / 100