제출 #1308323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308323		cyilliz	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	1 ms	332 KiB

apple

#include <bits/stdc++.h>

std::ifstream fin("f.in");
std::ofstream fout("f.out");

const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const int64_t LONG_INF = static_cast<int64_t>(1e18) + 5;

const int N = 1e9;

struct SegTree {
    struct node_t {
        int sum = 0;
        int lazy = -1;
        node_t *l = nullptr, *r = nullptr;
    };

    node_t *root = new node_t;

    void extend(node_t *node) {
        if (!node->l) {
            node->l = new node_t;
        }
        if (!node->r) {
            node->r = new node_t;
        }
    }

    void propagate(node_t *node, int low, int high) {
        if (node->lazy == -1) {
            return;
        }

        if (low != high) {
            extend(node);
            int mid = (low + high) / 2;
            node->l->sum = (mid - low + 1) * node->lazy;
            node->r->sum = (high - (mid + 1) + 1) * node->lazy;
            node->l->lazy = node->lazy;
            node->r->lazy = node->lazy;
        }
        node->lazy = -1;
    }

    void update(node_t *node, int low, int high, int ql, int qr, int new_val) {
        if (qr < low || high < ql) {
            return;
        }

        propagate(node, low, high);

        if (ql <= low && high <= qr) {
            node->lazy = new_val;
            node->sum = (high - low + 1) * new_val;
            return;
        }

        int mid = (low + high) / 2;
        extend(node);
        update(node->l, low, mid, ql, qr, new_val);
        update(node->r, mid + 1, high, ql, qr, new_val);
        node->sum = node->l->sum + node->r->sum;
    }

    int query(node_t *node, int low, int high, int ql, int qr) {
        if (qr < low || high < ql) {
            return 0;
        }

        propagate(node, low, high);

        if (ql <= low && high <= qr) {
            return node->sum;
        }

        int mid = (low + high) / 2;
        extend(node);
        return query(node->l, low, mid, ql, qr) + query(node->r, mid + 1, high, ql, qr);
    }
};

int queries, ans, last_ans;
SegTree seg;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    fin >> queries;
    while (queries--) {
        int type, x, y;
        fin >> type >> x >> y;
        x += last_ans;
        y += last_ans;
        x = std::max(1, std::min(N, x));
        y = std::max(1, std::min(N, y));
        if (x > y) {
            std::swap(x, y);
        }

        if (type == 1) {

            ans = seg.query(seg.root, 1, N, x, y);
            last_ans = ans;
            fout << ans << "\n";
        }
        else {
            seg.update(seg.root, 1, N, x, y, 1);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100