Submission #1262721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262721		papaulo	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	232 ms	144512 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val, lazy;
    Node *left, *right;
    Node() : val(0), lazy(0), left(nullptr), right(nullptr) {}
    void gen() {
        if(left) return;
        left=new Node();
        right=new Node();
    }
    void lazyPropagation(int l, int r) {
        if(!lazy) return;
        int sz=(r-l+1);
        val=sz;
        if(l<r) {
            gen();
            left->lazy=right->lazy=lazy;
        }
        this->lazy=0;
    }
    void update(int l, int r, int p, int q) {
        lazyPropagation(l, r);
        int sz=(r-l+1);
        if(val==sz) return;
        if(l>q||p>r) return;
        if(l>=p&&r<=q) {
            this->lazy=1;
            lazyPropagation(l, r);
            return;
        }
        gen();
        int mid=(l+r)/2;
        left->update(l, mid, p, q);
        right->update(mid+1, r, p, q);
        this->val=left->val+right->val;
    }
    int query(int l, int r, int p, int q) {
        lazyPropagation(l, r);
        if(l>q||p>r) return 0;
        if(l>=p&&r<=q) return val;
        gen();
        int mid=(l+r)/2;
        return left->query(l, mid, p, q)+right->query(mid+1, r, p, q);
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int m;
    cin >> m;
    Node nd;
    int c=0;
    ostringstream out;
    while(m--) {
        int d, x, y;
        cin >> d >> x >> y;
        if(d==1) {
            int val=nd.query(1, 1e9, x+c, y+c);
            c=val;
            out << val << endl;
        } else {
            nd.update(1, 1e9, x+c, y+c);
        }
    }
    cout << out.str();
}

• Subtask 1: 100 / 100