Submission #728487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
728487	2023-04-22T14:00:28 Z	ismayil	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	622 ms	132952 KB

apple

#pragma GCC target ("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int MOD = 1e9 + 7;
struct segtree{
    vector<int> tree, lazy, L, R;
    int size = 0;
    int create(){
        tree.push_back(0);
        lazy.push_back(0);
        L.push_back(0);
        R.push_back(0);
        return tree.size() - 1;
    }
    void init(int n){
        create();
        size = n;
        create();
    }
    void propagate(int x, int lx, int rx){
        if(lazy[x] == 0 || lx == rx) return;
        int mx = (lx + rx) / 2;
        if(!L[x]) L[x] = create();
        tree[L[x]] = mx - lx + 1;
        lazy[L[x]] = 1;
        if(!R[x]) R[x] = create();
        tree[R[x]] = rx - mx;
        lazy[R[x]] = 1;
        lazy[x] = 0;
    }
    void update(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return;
        if(l <= lx && rx <= r){
            tree[x] = rx - lx + 1;
            lazy[x] = 1;
            return;
        } 
        int mx = (lx + rx) / 2;
        if(!L[x]) L[x] = create();
        update(l, r, L[x], lx, mx);
        if(!R[x]) R[x] = create();
        update(l, r, R[x], mx + 1, rx);
        tree[x] = tree[L[x]] + tree[R[x]];
    }
    void update(int l, int r){
        update(l, r, 1, 1, size);
    }
    ll query(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return 0;
        if(l <= lx && rx <= r) return tree[x];
        int mx = (lx + rx) / 2;
        ll left = 0, right = 0;
        if(L[x]) left = query(l, r, L[x], lx, mx);
        if(R[x]) right = query(l, r, R[x], mx + 1, rx);
        return left + right;
    }
    ll query(int l, int r){
        return query(l, r, 1, 1, size);
    }
};
void solve(){
    int m;
    cin >> m;
    segtree st;
    st.init(1e9);
    int c = 0;
    while (m--)
    {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 1){
            c = st.query(x + c, y + c);
            cout << c << endl;
        }else st.update(x + c, y + c);
    }
    
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++){
        //printf("Case #%d: ", i);
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	21 ms	3360 KB	Output is correct
5	Correct	22 ms	3908 KB	Output is correct
6	Correct	22 ms	3792 KB	Output is correct
7	Correct	24 ms	3912 KB	Output is correct
8	Correct	168 ms	26940 KB	Output is correct
9	Correct	390 ms	45916 KB	Output is correct
10	Correct	405 ms	51292 KB	Output is correct
11	Correct	387 ms	55464 KB	Output is correct
12	Correct	388 ms	57324 KB	Output is correct
13	Correct	367 ms	85104 KB	Output is correct
14	Correct	377 ms	85144 KB	Output is correct
15	Correct	566 ms	128852 KB	Output is correct
16	Correct	572 ms	129852 KB	Output is correct
17	Correct	379 ms	85100 KB	Output is correct
18	Correct	404 ms	85344 KB	Output is correct
19	Correct	622 ms	132952 KB	Output is correct
20	Correct	563 ms	132876 KB	Output is correct