oj.uz

답안 #653839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653839 2022-10-28T12:36:00 Z Noble_Mushtak 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 468 ms 262144 KB 
//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

# 결과 실행 시간 메모리 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