Submission #1207356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207356		maryam	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	409 ms	327680 KiB

apple

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
void PRE() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
}
int n, q;
const ll sz = 2e18;
struct dynamicSeg {
    ll sum = 0;
    ll lazy = 0;  
    dynamicSeg* left = nullptr, * right = nullptr;
    void prop( ll nl, ll nr) {  
        if (lazy) {
            sum += 1 * (nr - nl + 1);
            sum = min(sum, nr - nl + 1);   
            lazy = 0;
            if (nl == nr)return;
            if (!left) left = new dynamicSeg();
            if (!right) right = new dynamicSeg();
            left->lazy = 1, right->lazy = 1;
        }
    }
    void add(ll nl, ll nr, ll i, ll j, ll delta) {
        prop(nl, nr);
        if (nl >= i && nr <= j) {
            lazy = 1;
            prop(nl, nr);
            return;
        }
        if (nl > j || nr < i)return;
        ll mid = nl + (nr - nl) / 2;
 
        if (!left) left = new dynamicSeg();
        if (!right) right = new dynamicSeg();
 
        left->add(nl, mid, i, j, delta);
        right->add(mid + 1, nr, i, j, delta);
        sum = left->sum + right->sum;
    }
    ll query(ll nl, ll nr, ll l, ll r) {
        prop(nl, nr);
        if (nl >= l && nr <= r)return sum;
        if (nl > r || nr < l)return 0;
        ll mid = nl + (nr - nl) / 2;
        auto res1 = left == nullptr ? 0 : left->query(nl, mid, l, r);
        auto res2 = right == nullptr ? 0 : right->query(mid + 1, nr, l, r);
        return  res1 + res2;
    }
};
int main() {
    PRE();
    int n; cin >> n;
    dynamicSeg dseg;
    ll c = 0;
    for (int i = 0; i < n; i++) {
        int d; cin >> d;
        ll l, r; cin >> l >> r;
        l += c, r += c;
        assert(l >= 1 && l <= sz && r >= 1 && r <= sz);
        if (d == 1) {
            c = dseg.query(0LL, sz - 1, l, r);
            cout << c << '\n';
        }
        else {
            dseg.add(0LL, sz - 1, l, r, 1LL);
        }
    }
 
    return 0; 
}

• Subtask 1: 0 / 100