Submission #1171808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171808		pg_mazen	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	370 ms	230544 KiB

apple

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

using namespace __gnu_pbds;
using namespace std;
using cd = complex<double>;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define el '\n'
#define sp ' '
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(), (v).rend()
#define YES cout << "YES\n"
#define Yes cout << "Yes\n"
#define yes cout << "yes\n"
#define NO cout << "NO\n"
#define No cout << "No\n"
#define no cout << "no\n"
//#define int long long
#define double long double
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll,ll>
#define loop int t; cin >> t; for(int i=1;i<=t;++i)
#define mms(arr, val) memset(arr, value, sizeof arr)

void PG_Mazen() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
}

const double EPS = 1e-7, PI = acos(-1);
const int N = 2e5 + 5, MOD = 1e9 + 7, oo = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int knightX[] = {-2, -2, 2, 2, 1, 1, -1, -1};
const int knightY[] = {-1, 1, -1, 1, -2, 2, -2, 2};
const ll ooo = 0x3f3f3f3f3f3f3f3f;

extern struct node *const EMPTY;

struct node {
    int value, lazy;
    node *l, *r;

    node() {
        value = lazy = 0;
        l = r = this;
    }

    node(int x) {
        value = lazy = x;
        l = r = EMPTY;
    }
};

node *const EMPTY = new node();

void propagate(node *&cur, int lx, int rx) {
    if (cur->lazy) {
        cur->value = cur->lazy * (rx - lx + 1);
        if (lx != rx) {
            if (cur->l == EMPTY) cur->l = new node(0);
            if (cur->r == EMPTY) cur->r = new node(0);
            cur->l->lazy = cur->lazy;
            cur->r->lazy = cur->lazy;
        }
        cur->lazy = 0;
    }
}

void update(int l, int r, int v, node *&cur, int lx = 1, int rx = 1e9) {
    propagate(cur, lx, rx);
    if (r < lx || l > rx) return;
    if (cur == EMPTY) cur = new node(0);
    if (lx >= l && rx <= r) {
        cur->lazy = v;
        propagate(cur, lx, rx);
        return;
    }
    int mid = lx + (rx - lx) / 2;
    update(l, r, v, cur->l, lx, mid);
    update(l, r, v, cur->r, mid + 1, rx);
    cur->value = cur->l->value + cur->r->value;
}

int query(int ql, int qr, node *&cur, int lx = 1, int rx = 1e9) {
    if (ql > rx || qr < lx) return 0;
    if (cur == EMPTY) return 0;
    propagate(cur, lx, rx);
    if (ql <= lx && qr >= rx) return cur->value;
    int mid = lx + (rx - lx) / 2;
    return query(ql, qr, cur->l, lx, mid) + query(ql, qr, cur->r, mid + 1, rx);
}


void testCase() {
    int q, c = 0;
    cin >> q;
    node *root = EMPTY;
    while (q--) {
        int i, l, r;
        cin >> i >> l >> r;
        l += c, r += c;
        if (i == 1) {
            c = query(l, r, root);
            cout << c << el;
        } else
            update(l, r, 1, root);
    }
}

int32_t main() {
    PG_Mazen();
    //sieve();
    //sieveSPF();
    //precompute();
    testCase();
    //cerr << clock() / 1000.0 << " Secs";
}

• Subtask 1: 100 / 100