제출 #1204463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204463		retired_zied	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	129 ms	327680 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define endl '\n'
#define pb push_back
const int N = 300005;

struct node {
    long long sum, lzAdd, lzSet;

    void set(long long v, int ns, int ne) {
        sum = v * (ne - ns + 1);
        lzSet = v;
        lzAdd = 0;
    }

    void add(long long v, int ns, int ne) {
        sum += v * (ne - ns + 1);
        lzAdd += v;
    }
} nodes[N * 4]; // Increase size to accommodate compressed range

void pushDown(int ni, int ns, int ne) {
    if (ns == ne) return;
    int l = ni * 2 + 1, r = l + 1, m = ns + (ne - ns) / 2;
    if (nodes[ni].lzSet != -1) {
        nodes[l].set(nodes[ni].lzSet, ns, m);
        nodes[r].set(nodes[ni].lzSet, m + 1, ne);
        nodes[ni].lzSet = -1;
    }
    if (nodes[ni].lzAdd) {
        nodes[l].add(nodes[ni].lzAdd, ns, m);
        nodes[r].add(nodes[ni].lzAdd, m + 1, ne);
        nodes[ni].lzAdd = 0;
    }
}

int arr[N], n;

node merge(const node &a, const node &b) {
    return {a.sum + b.sum, 0, -1};
}

void build(int ni = 0, int ns = 0, int ne = n - 1) {
    nodes[ni] = {0, 0, -1}; // Initialize node
    if (ns == ne) {
        nodes[ni] = {arr[ns], 0, -1};
        return;
    }
    int l = ni * 2 + 1, r = l + 1, m = ns + (ne - ns) / 2;
    build(l, ns, m);
    build(r, m + 1, ne);
    nodes[ni] = merge(nodes[l], nodes[r]);
}

void update(int qs, int qe, int v, bool isAdd, int ni = 0, int ns = 0, int ne = n - 1) {
    if (qs > ne || qe < ns) return;
    if (qs <= ns && qe >= ne) {
        if (isAdd) {
            nodes[ni].add(v, ns, ne);
        } else {
            nodes[ni].set(v, ns, ne);
        }
        return;
    }
    pushDown(ni, ns, ne);
    int l = ni * 2 + 1, r = l + 1, m = ns + (ne - ns) / 2;
    update(qs, qe, v, isAdd, l, ns, m);
    update(qs, qe, v, isAdd, r, m + 1, ne);
    nodes[ni] = merge(nodes[l], nodes[r]);
}

node query(int qs, int qe, int ni = 0, int ns = 0, int ne = n - 1) {
    if (qs > ne || qe < ns) return {0, 0, -1};
    if (qs <= ns && qe >= ne) return nodes[ni];
    pushDown(ni, ns, ne);
    int l = ni * 2 + 1, r = l + 1, m = ns + (ne - ns) / 2;
    return merge(query(qs, qe, l, ns, m), query(qs, qe, r, m + 1, ne));
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);

    int m;
    cin >> m;
    vector<tuple<int, int, int>> events(m);
    for (int i = 0; i < m; i++) {
        int d, x, y;
        cin >> d >> x >> y;
        events[i] = {d, x, y};
    }

    // Coordinate compression
    set<int> points;
    int C = 0;
    for (auto [d, x, y] : events) {
        points.insert(x + C);
        points.insert(y + C);
        if (d == 1) C += 0; // Placeholder for query result
    }
    vector<int> sorted_points(points.begin(), points.end());
    map<int, int> point_to_index;
    for (int i = 0; i < sorted_points.size(); i++) {
        point_to_index[sorted_points[i]] = i;
    }
    n = sorted_points.size();

    // Initialize array for segment tree
    fill(arr, arr + n, 0); // All trees initially unripe
    build(); // Build segment tree

    // Process events
    vector<int> ans;
    C = 0;
    for (auto [d, x, y] : events) {
        int left = point_to_index[x + C];
        int right = point_to_index[y + C];
        if (d == 2) {
            // Update: set trees in [x+C, y+C] to red (1)
            update(left, right, 1, false);
        } else {
            // Query: count red trees in [x+C, y+C]
            int count = query(left, right).sum;
            ans.push_back(count);
            C = count; // Update C
        }
    }

    // Output results
    for (int x : ans) {
        cout << x << endl;
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

apple.cpp: In function 'int32_t main()':
apple.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen("f.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
apple.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("f.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100