Submission #1041268

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041268	2024-08-01T19:57:47 Z	Thunnus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	269 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;
        }
        int mid = (tl + tr) / 2;
        propagate();
        if(l <= mid)
            lc->update(l, r, val);
        if(r > mid)
            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;
        int mid = (tl + tr) / 2, sm1 = 0, sm2 = 0;
        propagate();
        if(l <= mid)
            sm1 = lc->query(l, r);
        if(r > mid)
            sm2 = rc->query(l, r);
        return sm1 + sm2;
    }
};

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	6388 KB	Output is correct
5	Correct	9 ms	7772 KB	Output is correct
6	Correct	13 ms	7564 KB	Output is correct
7	Correct	11 ms	7768 KB	Output is correct
8	Correct	81 ms	58256 KB	Output is correct
9	Correct	167 ms	100688 KB	Output is correct
10	Correct	174 ms	111440 KB	Output is correct
11	Correct	174 ms	119612 KB	Output is correct
12	Correct	189 ms	123488 KB	Output is correct
13	Correct	161 ms	143696 KB	Output is correct
14	Correct	157 ms	144980 KB	Output is correct
15	Runtime error	269 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-