Submission #1041276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041276	2024-08-01T20:03:40 Z	Thunnus	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	381 ms	207864 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 || !lc) 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

100.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	8 ms	4956 KB	Output is correct
5	Correct	10 ms	5980 KB	Output is correct
6	Correct	10 ms	5724 KB	Output is correct
7	Correct	9 ms	5980 KB	Output is correct
8	Correct	90 ms	43860 KB	Output is correct
9	Correct	189 ms	75604 KB	Output is correct
10	Correct	212 ms	84008 KB	Output is correct
11	Correct	209 ms	89952 KB	Output is correct
12	Correct	219 ms	92756 KB	Output is correct
13	Correct	204 ms	107928 KB	Output is correct
14	Correct	193 ms	108920 KB	Output is correct
15	Correct	357 ms	201952 KB	Output is correct
16	Correct	345 ms	203348 KB	Output is correct
17	Correct	218 ms	114848 KB	Output is correct
18	Correct	203 ms	114876 KB	Output is correct
19	Correct	377 ms	207724 KB	Output is correct
20	Correct	381 ms	207864 KB	Output is correct