Submission #980882

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980882	2024-05-12T14:46:52 Z	Hagry	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	348 KB

apple

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define Hagry ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vector<int>>;

const int OO = 1e9 + 5;
const int N = 2e5 + 5;
const int IDN = 0;
const int LAZY_IDN = 0;
struct node {
    ll sum, lazy;
    node *left, *right;

    node() : sum(0), lazy(0), left(NULL), right(NULL) {}

    void addChild() {
        left = new node();
        right = new node();
    }

    void push(int lx, int rx) {
        if (lazy) {
            sum += lazy * (rx - lx + 1);
            if (rx != lx) {
                if (left == NULL)addChild();
                left->lazy += lazy;
                right->lazy += lazy;
            }
            lazy = 0;
        }
    }

    void update(int l, int r, int val, int lx, int rx) {
        push(lx, rx);
        if (lx > r || l > rx) {
            return;
        }

        if (lx >= l && rx <= r) {
            lazy += val;
            push(lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;
        if (left == NULL)addChild();

        left->update(l, r, val, lx, mid);
        right->update(l, r, val, mid + 1, rx);
        sum = left->sum + right->sum;
    }

    ll query(int l, int r, int lx, int rx) {
        if (l > rx || lx > r) {
            return 0;
        }
        push(lx, rx);
        if (lx >= l && rx <= r) {
            return sum;
        }
        if(left != NULL){
            int mid = (lx + rx) / 2;
            return left->query(l, r, lx, mid) + right->query(l, r, mid + 1, rx);
        }
        else return 0;
    }

    void clear() {
        if (left != NULL) {
            left->clear();
            right->clear();
        }
        delete this;
    }
};

void TC() {

    node root;
    int m;
    cin >> m;



    int d, x, y, c = 0;
    for(int q=0; q<m; ++q){
        cin >> d >> x >> y;
        if(d == 1){
            int ans = root.query(x+c, y+c, 0, 1e9 + 5);
            cout << ans << "\n";
            c = ans;
        }
        else
            root.update(x+c, y+c, 1, 0, 1e9 + 5);
    }

}

int32_t main() {

    Hagry
    int t = 1;
//    cin >> t;
    while (t--) {
        TC();
        cout << '\n';
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Halted	0 ms	0 KB	-