Submission #980884

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980884	2024-05-12T14:48:03 Z	Hagry	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	389 ms	262144 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){
            ll 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	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	7612 KB	Output is correct
5	Correct	15 ms	9304 KB	Output is correct
6	Correct	14 ms	9048 KB	Output is correct
7	Correct	15 ms	9308 KB	Output is correct
8	Correct	141 ms	69580 KB	Output is correct
9	Correct	252 ms	118608 KB	Output is correct
10	Correct	325 ms	132688 KB	Output is correct
11	Correct	303 ms	143660 KB	Output is correct
12	Correct	289 ms	148304 KB	Output is correct
13	Correct	312 ms	181284 KB	Output is correct
14	Correct	290 ms	183636 KB	Output is correct
15	Runtime error	389 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-