Submission #878610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
878610	2023-11-25T00:41:29 Z	PagodePaiva	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	456 ms	262144 KB

apple

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e9;

struct Node{
    int value;
    int lazy;
    Node *lc, *rc;

    Node(){
        value = 0;
        lazy = 0;
        lc = NULL;
        rc = NULL;
    }

    void newnode(){
        if(lc == NULL) lc = new Node();
        if(rc == NULL) rc = new Node();
    }
};

Node* seg = new Node();

void unlazy(Node *current, int l, int r){
    if(current -> lazy == 0) return;
    current -> value = (r-l+1)*(current -> lazy);

    if(l < r){
        current -> newnode();
        current -> lc -> lazy = current -> lazy;
        current -> rc -> lazy = current -> lazy;    
    }
    current -> lazy = 0;
    return;
}

void update(Node *current, int l, int r, int val, int tl, int tr){
    // cout << tl << ' ' << tr << '\n';
    unlazy(current, tl, tr);
    if(tl > r or tr < l) return;
    if(l <= tl and tr <= r){
        current -> lazy = val;
        // cout << tl << ' ' << tr << '\n';
        // cout << current -> value << ' ' << current -> lazy << '\n';
        unlazy(current, tl, tr);
        // cout << current -> value << ' ' << current -> lazy << '\n';

        return;
    }

    int mid = (tl+tr)/2;
    current -> newnode();
    update(current -> lc, l, r, val, tl, mid);
    update(current -> rc, l, r, val, mid+1, tr);

    current -> value = current -> lc -> value + current -> rc -> value; 
    return;
}

int query(Node *current, int l, int r, int tl, int tr){
    // cout << tl << ' ' << tr << '\n';
    unlazy(current, tl, tr);
    if(tl > r or tr < l) return 0;
    if(l <= tl and tr <= r) {
        // cout << tl << ' ' << tr << '\n';
        // cout << current -> value << ' ' << current -> lazy << '\n';
        return current -> value;
    }
    
    int mid = (tl+tr)/2;
    current -> newnode();
    return query(current -> lc, l, r, tl, mid) + query(current -> rc, l, r, mid+1, tr);
}

int32_t main(){
    int q;
    cin >> q;

    int c = 0;
    while(q--){
        int d, l, r;
        cin >> d >> l >> r;
        l += c;
        r += c;

        if(d == 1){
            int res = query(seg, l, r, 1, N);
            c = res;
            cout << res << '\n';
        }

        else{
            update(seg, l, r, 1, 1, N);
        }
    }

    return 0;
}

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	28 ms	8640 KB	Output is correct
5	Correct	32 ms	10596 KB	Output is correct
6	Correct	26 ms	10068 KB	Output is correct
7	Correct	26 ms	10588 KB	Output is correct
8	Correct	204 ms	77780 KB	Output is correct
9	Correct	431 ms	132532 KB	Output is correct
10	Correct	410 ms	148640 KB	Output is correct
11	Correct	417 ms	161108 KB	Output is correct
12	Correct	417 ms	166556 KB	Output is correct
13	Correct	418 ms	207412 KB	Output is correct
14	Correct	403 ms	209136 KB	Output is correct
15	Runtime error	456 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-