Submission #992417

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
992417	2024-06-04T12:19:25 Z	KK_1729	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	19 ms	10148 KB

apple

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

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

struct Vertex{
    int left, right;
    int sum = 0; int lazy = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb){
        left = lb;
        right = rb;
    }

    
    void extend(){
        if (!left_child && left < right){
            int t = (left+right)/2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t+1, right);
        }
    }
    int intersection(int l, int r, int ql, int qr){
        return max(0ll, min(r, qr)-max(l, ql)+1);
    }
    void push(){
        if (lazy){
            left_child->lazy = 1;
            left_child->sum = left_child->right-left_child->left+1;

            right_child->lazy = 1;
            right_child->sum = right_child->right-right_child->left+1;
        }
    }
    void add(int l, int r){
        extend();
        if (lazy) return;
        if (left >= l && right <= r){
            lazy = 1;
            sum = right-left+1;
            return;
        }
        if (right < l || left > r) return;
        push();
        if (left_child){
            left_child->add(l, r);
            right_child->add(l, r);
            sum = left_child->sum+right_child->sum;
        }
    }

    int get_sum(int ql, int qr){
        if (ql <= left && right <= qr) return sum;
        if (right < ql || left > qr) return 0;
        extend();
        push();
        return left_child->get_sum(ql, qr)+right_child->get_sum(ql, qr);
    }
};

void solve(){
    Vertex root(0, 1000001);
    int c = 0;
    // root.add(1, 8);
    // root.add(2, 6);
    // cout << root.get_sum(6, 8) << endl;
    int m; cin >> m;
    while (m--){
        int d, x, y; cin >> d >> x >> y;
        if (d == 1){
            int e = root.get_sum(x+c, y+c);
            c = e;
            cout << e << endl;
        }else{
            root.add(x+c, y+c);
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	3932 KB	Output is correct
5	Correct	7 ms	4808 KB	Output is correct
6	Correct	6 ms	4772 KB	Output is correct
7	Correct	7 ms	4952 KB	Output is correct
8	Incorrect	19 ms	10148 KB	Output isn't correct
9	Halted	0 ms	0 KB	-