Submission #1143476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143476		ammahmed004	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	280 ms	171548 KiB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define ll long long
#define ld long double
//#define int long long
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define pb push_back
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int MOD = 1e9 + 7;
//const int MOD = 998244353  ;
const int N = 3e5 + 48;
const ll INF = 1e18;
const ll MIN = -1e18;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;


int Tree[32 * N];
int l_child[32 * N];
int r_child[32 * N];
int lazy[32 * N];
int upd[32 * N];
int cnt;

int get_val(int id) {
    if (id == -1)return 0;
    return Tree[id];
}

int creat() {
    Tree[cnt] = 0;
    lazy[cnt] = 0;
    upd[cnt] = 0;
    l_child[cnt] = r_child[cnt] = -1;
    return cnt++;
}

void unlazy(int id, int ns, int ne) {
    if (id == -1)return;
    if (upd[id] == 0) return;
    if (l_child[id] == -1) {
        l_child[id] = creat();
    }
    if (r_child[id] == -1) {
        r_child[id] = creat();
    }
    Tree[id] = (ne - ns + 1);
    lazy[l_child[id]] = lazy[r_child[id]] = lazy[id];
    upd[id] = 0;
    upd[r_child[id]] = upd[l_child[id]] = 1;
}

int query(int qs, int qe, int ns = 1, int ne = 1e9, int id = 0) {
    if (id == -1)return 0;
    unlazy(id, ns, ne);
    if (ne < qs || ns > qe) return 0;
    if (qs <= ns && ne <= qe) return Tree[id];
    int idl = l_child[id], idr = r_child[id], md = ns + (ne - ns) / 2;
    int one = query(qs, qe, ns, md, idl);
    int two = query(qs, qe, md + 1, ne, idr);
    return one + two;
}

int update(int qs, int qe, int val, int ns = 1, int ne = 1e9, int id = 0) {
    unlazy(id, ns, ne);
    if (qs > ne || qe < ns) return id;
    if (id == -1)id = creat();
    if (qs <= ns && ne <= qe) {
        lazy[id] = val;
        upd[id] = 1;
        unlazy(id, ns, ne);
        return id;
    }
    int md = ns + (ne - ns) / 2;
    int idl = l_child[id];
    int idr = r_child[id];
    l_child[id] = update(qs, qe, val, ns, md, idl);
    r_child[id] = update(qs, qe, val, md + 1, ne, idr);
    Tree[id] = get_val(l_child[id]) + get_val(r_child[id]);
    return id;
}


void solve() {
    cnt = 0;
    creat();
    ll c = 0;
    ll q;cin >> q;
    while (q--) {
        ll d, x, y; cin >> d >> x >> y;
        if (d == 1) {
            c = query(x + c, y + c);
            cout << c << endl;
        }
        else {
            update(x + c, y + c, 1);
        }
    }
}

signed main() {
    FAST;
    ll t = 1;
    //cin>>t;
    while (t--) solve();
}

• Subtask 1: 100 / 100