Submission #1282566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282566		ihateojuz	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	276 ms	79120 KiB

apple

#define _CRT_SECURE_NO_WARNINGS

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize ("O3")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Babahnineeleven will win IOI 2040
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Pavlyk is best coder in Khmelnytskiiii

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
//#include <unordered_set>
//#include <unordered_map>
#include <bitset>
#include <cstring> // �л� memset

using namespace std;

#define endl '\n'

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <ll, ll> pii;
typedef std::pair <ll, ull> piu;
typedef std::pair <ld, ld> pdd;

const ll DIM = 5000007;
const ll SQDIM = 450;
const ll MXMASK = (1 << 20);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 32;
const ll Bsize = 1000;
const char endL = '\n';

const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };

FILE* stream;

class segmentTree {
public:

    void init(int sz_, int mxSize) {
        sz = sz_;
        T.resize(mxSize);

        T[0] = { -1, -1, 0, 0 };

        allNodes = 1;
    }

    int query(int L, int R) {
        return query(0, 1, sz, L, R);
    }

    void update(int L, int R) {
        update(0, 1, sz, L, R);
    }

private:

    struct node
    {
        int l, r;
        int val, cnt;

        node() {
            l = -1;
            r = -1;
            val = 0;
            cnt = 0;
        }

        node(int l_, int r_, int val_, int cnt_) {
            l = l_;
            r = r_;
            val = val_;
            cnt = cnt_;
        }
    };

    void push(int v, int tl, int tr) {
        if (T[v].l == -1) T[v].l = allNodes++;
        if (T[v].r == -1) T[v].r = allNodes++;

        if (T[v].val) {
            int tm = (tl + tr) / 2;

            T[T[v].l].val = 1;
            T[T[v].l].cnt = tm - tl + 1;
            
            T[T[v].r].val = 1;
            T[T[v].r].cnt = tr - tm;
        }
    }

    int query(int v, int tl, int tr, int L, int R) {
        if (v == -1 || tl > R || tr < L) return 0;
        if (L <= tl && tr <= R) return T[v].cnt;

        push(v, tl, tr);

        int tm = (tl + tr) / 2;

        return query(T[v].l, tl, tm, L, R) + query(T[v].r, tm + 1, tr, L, R);
    }

    void update(int v, int tl, int tr, int L, int R) {
        if (v == -1 || tl > R || tr < L) return;
        if (L <= tl && tr <= R) {
            T[v] = { T[v].l, T[v].r, 1, tr - tl + 1 };
            return;
        }

        push(v, tl, tr);

        int tm = (tl + tr) / 2;
        update(T[v].l, tl, tm, L, R);
        update(T[v].r, tm + 1, tr, L, R);

        T[v].cnt = 0;
        if (T[v].l != -1) T[v].cnt += T[T[v].l].cnt;
        if (T[v].r != -1) T[v].cnt += T[T[v].r].cnt;
    }

    int sz, allNodes;
    vector < node > T;

};

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef _DEBUG
    freopen_s(&stream, "input.txt", "r", stdin);
    freopen_s(&stream, "output.txt", "w", stdout);
#endif

    int m;
    cin >> m;

    segmentTree t;
    t.init(1e9, DIM);

    int c = 0;
    for (int i = 1; i <= m; i++) {
        int type, l, r;
        cin >> type >> l >> r;

        if (type == 1) {
            c = t.query(l + c, r + c);
            cout << c << endl;
        }
        else {
            t.update(l + c, r + c);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100