Submission #1242542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242542		albfr	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	291 ms	205636 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MOD 1000000007
#define INF ((ll)1e9)
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define rep(a, b, c) for (ll a=(b);(a)<(c);++(a))
#define LINE cerr << " ===================== " << endl
#define DBG(x) cerr << #x << " = " << (x) << endl

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef array<int, 3> tii;
typedef array<ll, 3> tll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvii;
typedef vector<vector<ll>> vvll;

ostream & operator <<(ostream &os, const tll &t) {
    return os << "(" << t[0] << "," << t[1] << "," << t[2] << ")";
}

ostream & operator <<(ostream &os, const pll &p) {
   return os << "(" << p.F << "," << p.S << ")";
}

template <typename T>
ostream & operator <<(ostream &os, const vector<T> &v) {
    os << "[";
    rep(i, 0, sz(v)) {
        if (i > 0) os << ",";
        os << v[i];
    }
    return os << "]";
}

struct Vertex {
    int left, right;
    int sum = 0;
    int upd = 0;
    int upd_v = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
        // sum = v;
    }

    void extend() {
        if (!left_child && left < right) {
            int t = (left + right) / 2;
            // ll v = 0;
            // if (sum) v = sum/2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t+1, right);
        }
    }

    void update(int l, int r, ll x) {
        // cerr << "Node: [" << left << "," << right << "] = " << sum << "\n";
        // cerr << left << " " << right << "\n";
        if (l <= left and right <= r) {
            sum = x * (right-left+1);
            upd_v = x;
            upd = 1;
            // cerr << "leaf Node: [" << left << "," << right << "] = " << sum << "\n";
            // upd = x;
            return;
        }
        // upd = 0;
        if (r < left or right < l)
            return;
        extend();
        if (left < right) {
            if (upd) {
                left_child->propagate(upd_v);
                right_child->propagate(upd_v);
                upd = 0;
            }
            left_child->update(l, r, x);
            right_child->update(l, r, x);
            upd = 0;
            sum = left_child->sum + right_child->sum;
            // cerr << "Node " << left << " " << right << " updated its sum to " << sum << "\n";
        }
    }

    void propagate(ll x) {
        sum = x * (right-left+1);
        upd_v = x;
        upd = 1;
    }

    int get_sum(int lq, int rq) {
        if (lq <= left and right <= rq) {
            // cerr << "Totally contained, returning " << sum << " on " << left << " " << right << "\n";
            return sum;
        }
        if (rq < left or right < lq)
            return 0;
        extend();
        if (upd) {
            left_child->propagate(upd_v);
            right_child->propagate(upd_v);
        }
        upd = 0;
        sum = left_child->sum + right_child->sum;
        return left_child->get_sum(lq, rq) + right_child->get_sum(lq, rq);
    }
};

inline void solve_case() {
    ll m;
    cin >> m;
    Vertex *root = new Vertex(1, 1e9+1);
    // Vertex *root = new Vertex(1, 1);
    int d, x, y;
    int c = 0;
    while (m--) {
        cin >> d >> x >> y;
        if (d == 2) {
            root->update(x+c, y+c, 1);
            // ll sum = root->get_sum(x, y);
            // DBG(sum);
        }
        else {
            int r = root->get_sum(x+c, y+c);
            cout << r << "\n";
            c = r;
        }
        // LINE;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
    // cin >> tc;
    rep(t, 0, tc) solve_case();
}

• Subtask 1: 100 / 100