Submission #1275972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275972		masterofcpp	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	278 ms	260480 KiB

apple

/*
            ,___________________________________________/7_
           |-_______------. `\                             |
       _,/ | _______)     |___\____________________________|
  .__/`((  | _______      | (/))_______________=.
     `~) \ | _______)     |   /----------------_/
       `__y|______________|  /
       / ________ __________/
      / /#####\(  \  /     ))
     / /#######|\  \(     //
    / /########|.\______ad/`
   / /###(\)###||`------``
  / /##########||
 / /###########||
( (############||
 \ \####(/)####))
  \ \#########//
   \ \#######//
    `---|_|--`
       ((_))
        `-`
*/

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define bigint __int128
#define int long long
#define double long double
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define stop(msg) {cout<<msg; return;}
#define all(aba) aba.begin(), aba.end()
#define rall(aba) aba.rbegin(), aba.rend()
#define take(aba) for (int abab=0; abab<aba.size(); abab++) cin>>aba[abab]
#define print(aba,sep) for (auto abab : aba) cout<<abab<<sep
#define pprint(aba,sep1,sep2) for (int abab=0; abab<aba.size(); abab++) cout<<aba[abab].F<<sep1<<aba[abab].S<<sep2
#define line "-------------------\n"
#define nline "\n-------------------\n"
#define linen "-------------------\n"

/// find_by_order (index), order_of_key (lower bound)
template<typename t>
using indexed_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename t>
using indexed_multiset = tree<t, null_type, less_equal<t>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int rand(int l, int r) {return rng()%(r-l+1)+l;}

double estimate_time(double n) {
    double a = 7.1e-9, b = 0.02;
    return max((double)0, a*n+b);
}

// O(1e8) = 1s.

const int MOD = (int)1e9;
const int N = (int)1e5+5;
const int LG = (int)32;
const int INF = (int)1e18;
const int TREESIZE = (int)N*LG*4;

struct Node{
    int lchild, rchild, res, lazy;
};

int last=1;
Node st[TREESIZE];
void extend(int idx){
    if (st[idx].lchild) return;
    st[idx].lchild = ++last;
    st[idx].rchild = ++last;
}

void relax(int v, int l, int r){
    if (!st[v].lazy) return;
    st[v].res = r-l+1;
    if (l != r){
        extend(v);
        st[st[v].lchild].lazy = st[st[v].rchild].lazy = 1;
    }
    st[v].lazy = 0;
}

void update(int v, int l, int r, int ql, int qr){
    relax(v, l, r);
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr){
        st[v].lazy = 1;
        relax(v, l, r);
        return;
    }
    int mid = (l+r)/2;
    extend(v);
    update(st[v].lchild, l, mid, ql, qr);
    update(st[v].rchild, mid+1, r, ql, qr);
    st[v].res = st[st[v].lchild].res + st[st[v].rchild].res;
}

int ask(int v, int l, int r, int ql, int qr){
    relax(v, l, r);
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return st[v].res;
    int mid = (l+r)/2;
    return ask(st[v].lchild, l, mid, ql, qr) + ask(st[v].rchild, mid+1, r, ql, qr);
}

void solve(){
    int n=1e9+5, q, C=0; cin>>q;
    while (q--){
        int cmd,l,r; cin>>cmd>>l>>r;
        l+=C; r+=C;
        if (cmd == 1){
            int ans = ask(1, 1, n, l, r);
            cout<<ans<<endl;
            C = ans;
        } else update(1, 1, n, l, r);
    }
}

signed main(){
    Fast;
    int t=1;
    //cin>>t;
    for (int i=1; i<=t; i++) {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100