Submission #653839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
653839	2022-10-28T12:36:00 Z	Noble_Mushtak	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	468 ms	262144 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	6004 KB	Output is correct
5	Correct	19 ms	7188 KB	Output is correct
6	Correct	20 ms	6872 KB	Output is correct
7	Correct	19 ms	7116 KB	Output is correct
8	Correct	142 ms	52376 KB	Output is correct
9	Correct	293 ms	89336 KB	Output is correct
10	Correct	291 ms	99828 KB	Output is correct
11	Correct	317 ms	108244 KB	Output is correct
12	Correct	314 ms	111912 KB	Output is correct
13	Correct	281 ms	139068 KB	Output is correct
14	Correct	287 ms	140508 KB	Output is correct
15	Correct	446 ms	254488 KB	Output is correct
16	Correct	468 ms	256440 KB	Output is correct
17	Correct	285 ms	145320 KB	Output is correct
18	Correct	301 ms	145408 KB	Output is correct
19	Correct	443 ms	262144 KB	Output is correct
20	Correct	454 ms	262144 KB	Output is correct