Submission #991485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991485	2024-06-02T09:54:22 Z	onebit1024	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	337 ms	170648 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"

const double PI=3.141592653589;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

struct segtree{
    vector<int>seg,left,right,lazy;
    int sz = 1;
    int curr = 0;
    void init(int n){
        while(sz < n)sz*=2;
        seg.pb(0);
        lazy.pb(0);
        left.pb(-1);
        right.pb(-1);
    }

    int get_node(){
        left.pb(-1);
        lazy.pb(0);
        right.pb(-1);
        seg.pb(0);
        curr++;
        return curr;
    }

    void upd(int x, int lx, int rx, int l, int r){
        if(right[x]==-1)right[x] = get_node();
        if(left[x] == -1)left[x] = get_node();

        if(lazy[x]){
            seg[x] = rx-lx;
            if(rx-lx > 1){
                lazy[left[x]] = 1;
                lazy[right[x]] = 1;
            }
            lazy[x] = 0;
        }
        if(lx >= l && rx <= r){
            seg[x] = rx-lx;
            if(rx-lx > 1){
                lazy[left[x]] = 1;
                lazy[right[x]] = 1;
            }
            return;
        }
        if(rx <=l || lx >= r)return;
        int m= (lx+rx)/2;

        upd(left[x],lx,m,l,r);
        upd(right[x],m,rx,l,r);
        seg[x] = seg[right[x]] + seg[left[x]];
    }       

    void upd(int l, int r){
        upd(0,0,sz,l,r);
    }

    int sol(int x, int lx, int rx, int l, int r){
        if(right[x]==-1)right[x] = get_node();
        if(left[x] == -1)left[x] = get_node();

        if(lazy[x]){
            seg[x] = rx-lx;
            if(rx-lx > 1){
                lazy[left[x]] = 1;
                lazy[right[x]] = 1;
            }
            lazy[x] = 0;
        }

        if(lx >= l && rx <= r)return seg[x];
        if(rx <=l || lx >= r)return 0ll;
        int m = (lx+rx)/2;
        return sol(left[x],lx,m,l,r) + sol(right[x],m,rx,l,r);
    }

    int sol(int l, int r){
        return sol(0,0,sz,l,r);
    }
};

void solve()
{
    int q;cin>> q;
    segtree st;
    st.init(1e9+5);
    int c = 0;
    while(q--){
        int t;cin >> t;
        int l,r;cin >> l >> r;
        if(t==2){
            st.upd(c+l,c+r+1);
        }else{
            c = st.sol(c+l,c+r+1);        cout << c << endl;

        }
    }
}   

int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    

    int T=1;
    for(int i = 1;i<=T;++i)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	11 ms	3688 KB	Output is correct
5	Correct	13 ms	4272 KB	Output is correct
6	Correct	14 ms	4052 KB	Output is correct
7	Correct	14 ms	4276 KB	Output is correct
8	Correct	98 ms	30736 KB	Output is correct
9	Correct	205 ms	52264 KB	Output is correct
10	Correct	188 ms	62260 KB	Output is correct
11	Correct	212 ms	64044 KB	Output is correct
12	Correct	215 ms	63600 KB	Output is correct
13	Correct	188 ms	84264 KB	Output is correct
14	Correct	197 ms	88100 KB	Output is correct
15	Correct	337 ms	168980 KB	Output is correct
16	Correct	309 ms	170064 KB	Output is correct
17	Correct	195 ms	87904 KB	Output is correct
18	Correct	189 ms	86828 KB	Output is correct
19	Correct	322 ms	170248 KB	Output is correct
20	Correct	323 ms	170648 KB	Output is correct