Submission #991480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991480	2024-06-02T09:49:32 Z	onebit1024	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	342 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);
        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(1e10);
    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	348 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	6820 KB	Output is correct
5	Correct	15 ms	8100 KB	Output is correct
6	Correct	16 ms	7836 KB	Output is correct
7	Correct	15 ms	8092 KB	Output is correct
8	Correct	111 ms	63064 KB	Output is correct
9	Correct	228 ms	104716 KB	Output is correct
10	Correct	251 ms	122672 KB	Output is correct
11	Correct	237 ms	130068 KB	Output is correct
12	Correct	249 ms	129804 KB	Output is correct
13	Correct	221 ms	172212 KB	Output is correct
14	Correct	230 ms	170060 KB	Output is correct
15	Runtime error	342 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-