제출 #1308328

#제출 시각아이디문제언어결과실행 시간메모리
1308328cyilliz원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>

std::ifstream fin("date.in");
std::ofstream fout("date.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 node_t {
    int sum = 0;
    int lazy = -1;
    int low, high;
    node_t *l = nullptr, *r = nullptr;

    node_t(int _low, int _high)
        : low(_low), high(_high) {
    }

    void extend() {
        if (low == high) {
            return;
        }
        int mid = (low + high) / 2;
        if (!l) {
            l = new node_t(low, mid);
        }
        if (!r) {
            r = new node_t(mid + 1, high);
        }
    }

    void propagate() {
        if (low == high) {
            return;
        }
        extend();
        if (lazy != -1) {
            l->lazy = r->lazy = lazy;
            l->sum = (l->high - l->low + 1) * lazy;
            r->sum = (r->high - r->low + 1) * lazy;
            lazy = -1;
        }
    }

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

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

        propagate();
        l->update(ql, qr, new_val);
        r->update(ql, qr, new_val);
        sum = l->sum + r->sum;
    }

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

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

        propagate();
        return l->query(ql, qr) + r->query(ql, qr);
    }
};

int queries, ans, last_ans;
node_t *seg = new node_t(1, N);

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(x, y);
            last_ans = ans;
            fout << ans << "\n";
        }
        else {
            seg->update(x, y, 1);
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...