제출 #1273645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273645		amigoo99234	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	0 ms	332 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 = 1e9 + 5, 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)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 = -N, int r = N) {
    if (!x) x = new Node();
    pushDown(x, l, r);
    if (l >= ql && r <= qr) {
        x->sum += val * (r - l + 1);
        x->lazy += val;
        return;
    }
    if (qr < l || ql > r)return;
    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 = -N, int nr = N) {
    if (!x)return 0;
    pushDown(x, l, r);
    if (nl >= l && nr <= r) {
        return x->sum;
    }
    if (nr < l || nl > r)return 0;
    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;
            if (d == 1) {
                int ans = qry(l + c, r + c, root);
                cout << ans << '\n';
                c = ans;
            } else {
                upd(l + c, r + c, 1, root);
            }
        }
    }
}

• Subtask 1: 0 / 100