Submission #653839

#	Time	Username	Problem	Language	Result	Execution time	Memory
653839		Noble_Mushtak	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	468 ms	262144 KiB

apple

//replace Ofast with O3 for floating-point accuracy
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>

using num = int64_t;
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define REPI(t, n) for (num t = 0; t < n; ++t)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef TESTING
#define DEBUG(...) __VA_ARGS__
#else
#define DEBUG(...)
#endif

using value = int64_t;
using upd = int64_t;
const value IDENT = 0; //Change as needed
const upd NONE = 0;
static value mergeValues(value val1, value val2) { return val1+val2; }
static void updNode(value &curValue, num left, num right, upd newUpd) { curValue = (right-left+1)*newUpd; }
static void mergeUpdates(upd &origUpd, upd newUpd) { origUpd = newUpd; }
constexpr num MAXQ = 200000;
struct node;
struct nalloc {
    vector<node> nodes;
    num newNode();
    nalloc() { nodes.reserve(64*MAXQ); }
};
struct node {
    value val; upd lz; num l, r;
    node() : val(IDENT), lz(NONE), l(-1), r(-1) {}
};
num nalloc::newNode() {
    nodes.push_back(node());
    return sz(nodes)-1;
}
struct segtree {
    num N, root;
    nalloc *na;
    segtree(nalloc *ourNa, num n) : N(n), na(ourNa) {
        root = na->newNode();
    }
    void create(num &nidx) { if (nidx == -1) { nidx = na->newNode(); } }
    void push(num nidx, num left, num right) {
        if (na->nodes[nidx].lz != NONE) {
            updNode(na->nodes[nidx].val, left, right, na->nodes[nidx].lz);
            if (left != right) {
                create(na->nodes[nidx].l), create(na->nodes[nidx].r);
                mergeUpdates(na->nodes[na->nodes[nidx].l].lz, na->nodes[nidx].lz);
                mergeUpdates(na->nodes[na->nodes[nidx].r].lz, na->nodes[nidx].lz);
            }
            na->nodes[nidx].lz = 0;
        }
    }
    value query(num leftQ, num rightQ, num nidx = -2, num left = 0, num right = -1) {
        if (nidx == -2) nidx = root, right = N-1;
        assert(nidx != -1);
        push(nidx, left, right);
        if (right < leftQ || left > rightQ) return IDENT;
        if (left >= leftQ && right <= rightQ) return na->nodes[nidx].val;
        num mid = (left+right)/2;
        create(na->nodes[nidx].l), create(na->nodes[nidx].r);
        return mergeValues(query(leftQ, rightQ, na->nodes[nidx].l, left, mid),
                           query(leftQ, rightQ, na->nodes[nidx].r, mid+1, right));
    }
    void update(num leftU, num rightU, upd newUpd, num nidx = -2, num left = 0, num right = -1) {
        if (nidx == -2) nidx = root, right = N-1;
        assert(nidx != -1);
        push(nidx, left, right);
        if (right < leftU || left > rightU) return;
        if (left >= leftU && right <= rightU) { na->nodes[nidx].lz = newUpd; push(nidx, left, right); return; }
        num mid = (left+right)/2;
        create(na->nodes[nidx].l), create(na->nodes[nidx].r);
        update(leftU, rightU, newUpd, na->nodes[nidx].l, left, mid);
        update(leftU, rightU, newUpd, na->nodes[nidx].r, mid+1, right);
        na->nodes[nidx].val = mergeValues(na->nodes[na->nodes[nidx].l].val,
                                          na->nodes[na->nodes[nidx].r].val);
    }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    nalloc na;
    segtree curTree(&na, (num)(1e9+1));
    num M;
    cin >> M;
    num C = 0;
    while (M--) {
        num D, X, Y;
        cin >> D >> X >> Y;
        X += C;
        Y += C;
        if (D == 1) {
            C = curTree.query(X, Y);
            cout << C << "\n";
        } else {
            curTree.update(X, Y, 1);
        }
    }
}

• Subtask 1: 100 / 100