Submission #991483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991483	2024-06-02T09:53:10 Z	onebit1024	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	361 ms	262144 KB

apple

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

#define int long long
#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

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	13 ms	6564 KB	Output is correct
5	Correct	15 ms	8100 KB	Output is correct
6	Correct	15 ms	7844 KB	Output is correct
7	Correct	16 ms	8072 KB	Output is correct
8	Correct	114 ms	65040 KB	Output is correct
9	Correct	268 ms	106512 KB	Output is correct
10	Correct	244 ms	116752 KB	Output is correct
11	Correct	259 ms	126992 KB	Output is correct
12	Correct	271 ms	127956 KB	Output is correct
13	Correct	251 ms	170932 KB	Output is correct
14	Correct	240 ms	169552 KB	Output is correct
15	Runtime error	361 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-