Submission #1041261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041261	2024-08-01T19:51:51 Z	Thunnus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	277 ms	262144 KB

apple

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct Vertex{
    int sum = 0, lazy_set = 0, tl, tr;
    Vertex *lc = nullptr, *rc = nullptr;
    Vertex(int lb, int rb){
        tl = lb, tr = rb;
    }

    inline void extend(){
        if(!lc){
            int mid = (tl + tr) / 2;
            lc = new Vertex(tl, mid);
            rc = new Vertex(mid + 1, tr);
        }
    }

    inline void propagate(){
		extend();
        if(!lazy_set) return;
        int mid = (tl + tr) / 2;
        lc->lazy_set = rc->lazy_set = lazy_set;
        lc->sum = (mid - tl + 1) * lazy_set;
        rc->sum = (tr - mid) * lazy_set;
        lazy_set = 0;
    }

    void update(int l, int r, int val){
        if(r < tl || l > tr) return;
        if(r >= tr && l <= tl){
            sum = (tr - tl + 1) * val;
            lazy_set = val;
            return;
        }
        propagate();
        lc->update(l, r, val);
        rc->update(l, r, val);
        sum = lc->sum + rc->sum;
    }

    int query(int l, int r){
        if(r < tl || l > tr) return 0ll;
        if(r >= tr && l <= tl) return sum;
        propagate();
        return lc->query(l, r) + rc->query(l, r);
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    Vertex st(1, 1e9);
    int m, type, l, r, c = 0;
    cin >> m;
    while(m--){
        cin >> type >> l >> r;
        if(type == 1){
            c = st.query(l + c, r + c);
            cout << c << "\n";
        }
        else{
            st.update(l + c, r + c, 1);
        }
    }
    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	8 ms	6612 KB	Output is correct
5	Correct	9 ms	8028 KB	Output is correct
6	Correct	9 ms	7620 KB	Output is correct
7	Correct	9 ms	7772 KB	Output is correct
8	Correct	85 ms	58960 KB	Output is correct
9	Correct	176 ms	102268 KB	Output is correct
10	Correct	169 ms	112996 KB	Output is correct
11	Correct	170 ms	121420 KB	Output is correct
12	Correct	184 ms	125136 KB	Output is correct
13	Correct	159 ms	145688 KB	Output is correct
14	Correct	162 ms	147028 KB	Output is correct
15	Runtime error	277 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-