Submission #1171780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171780		pg_mazen	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	442 ms	230596 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;

struct node {
private:
    int value, lazy;
    node *left, *right;

public:
    node() {
        value = lazy = 0;
        left = right = nullptr;
    }

private:
    void addChild() {
        left = new node();
        right = new node();
    }

    void propagate(int lx, int rx) {
        if (lazy) {
            value = lazy * (rx - lx + 1);
            if (rx != lx) {
                if (left == nullptr) addChild();
                left->lazy = lazy;
                right->lazy = lazy;
            }
            lazy = 0;
        }
    }

public:
    void update(int l, int r, int val, int lx = 1, int rx = 1e9) {
        propagate(lx, rx);
        if (lx > r || l > rx) return;
        if (lx >= l && rx <= r) {
            lazy = val;
            propagate(lx, rx);
            return;
        }

        int mid = lx + (rx - lx) / 2;
        if (left == nullptr) addChild();

        left->update(l, r, val, lx, mid);
        right->update(l, r, val, mid + 1, rx);
        value = left->value + right->value;
    }

    int query(int l, int r, int lx = 1, int rx = 1e9) {
        if (l > rx || lx > r) return 0;
        propagate(lx, rx);
        if (lx >= l && rx <= r) {
            return value;
        }
        if (left != nullptr) {
            int mid = lx + (rx - lx) / 2;
            return left->query(l, r, lx, mid) + right->query(l, r, mid + 1, rx);
        }
        return 0;
    }

    void clear() {
        if (left != nullptr) {
            left->clear();
            right->clear();
        }
        delete this;
    }
} *root = new node();


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

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

• Subtask 1: 100 / 100