Submission #1041274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041274	2024-08-01T20:01:25 Z	Thunnus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	278 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;
    }

    ~Vertex(){
        delete lc;
        delete rc;
    }
 
    inline void extend(){
        if(!lc && tl != tr){
            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	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	11 ms	6456 KB	Output is correct
5	Correct	13 ms	7640 KB	Output is correct
6	Correct	17 ms	7516 KB	Output is correct
7	Correct	12 ms	7772 KB	Output is correct
8	Correct	108 ms	58196 KB	Output is correct
9	Correct	224 ms	100868 KB	Output is correct
10	Correct	225 ms	111440 KB	Output is correct
11	Correct	233 ms	119628 KB	Output is correct
12	Correct	252 ms	123392 KB	Output is correct
13	Correct	219 ms	143788 KB	Output is correct
14	Correct	246 ms	145072 KB	Output is correct
15	Runtime error	278 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-