제출 #1198415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198415		khalwsh	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	396 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);
// #ifndef ONLINE_JUDGE
//     freopen("in.txt", "r", stdin);
//     freopen("out.txt", "w", stdout);
//     freopen("error.txt", "w", stderr);
// #endif
}
int n , q;
const int sz = 2e9;
struct dynamicSeg {
    ll sum = 0;
    int lazy = 0;
    dynamicSeg *left = nullptr, *right = nullptr;
    void prop(int nl , int nr) {
        if (lazy) {
            sum += 1 * (nr - nl + 1);
            sum = min(sum , 0LL + 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(int nl , int nr , int i , int j , int delta) {
        prop(nl , nr);
        if (nl >= i && nr <= j) {
            lazy = 1;
            prop(nl , nr);
            return;
        }
        if (nl > j || nr < i)return;
        int 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;
    }
    int query(int nl , int nr , int l , int r) {
        prop(nl , nr);
        if (nl >= l && nr <= r)return sum;
        if (nl > r || nr < l)return 0;
        int 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(0 , sz - 1 , l , r);
            cout<<c<<'\n';
        }else {
            dseg.add(0 , sz - 1 , l , r , 1);
        }
    }
}

• Subtask 1: 0 / 100