제출 #1280394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280394		heymynameiskira	푸드 코트 (JOI21_foodcourt)	C++20	13 / 100	280 ms	45260 KiB

foodcourt

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

class Fenwick {
    private:
        vector<ll> val;
    public:
        Fenwick(int n) : val(n+1, 0) {}

        // Adds v to index i
        void add(int i, ll v) {
            for (++i; i < val.size(); i += i & -i) {
                val[i] += v;
            }
        }

        // Calculates prefix sum up to index i
        ll get(int i) {
            ll res = 0;
            for (++i; i > 0; i -= i & -i) {
                res += val[i];
            }
            return res;
        }
        ll get(int a, int b) { return get(b) - get(a-1); }
};

// Segment tree for range minimum and addition.
class SegTree {
    private:
        const ll NEUT = 4 * (ll)1e18;
        vector<ll> seg, tag;
        int h = 1;

        void apply(int i, ll v) {
            seg[i] += v;
            if (i < h) tag[i] += v;
        }
        void push(int i) {
            if (tag[i] == 0) return;
            apply(2*i, tag[i]);
            apply(2*i+1, tag[i]);
            tag[i] = 0;
        }
        ll combine(ll a, ll b) { return min(a, b); }

        ll recGet(int a, int b, int i, int ia, int ib) {
            if (ib <= a || b <= ia) return NEUT;
            if (a <= ia && ib <= b) return seg[i];
            push(i);
            int im = (ia + ib) >> 1;
            return combine(
                recGet(a, b, 2*i, ia, im),
                recGet(a, b, 2*i+1, im, ib));
        }
        void recApply(int a, int b, ll v, int i, int ia, int ib) {
            if (ib <= a || b <= ia) return;
            if (a <= ia && ib <= b) apply(i, v);
            else {
                push(i);
                int im = (ia + ib) >> 1;
                recApply(a, b, v, 2*i, ia, im);
                recApply(a, b, v, 2*i+1, im, ib);
                seg[i] = combine(seg[2*i], seg[2*i+1]);
            }
        }
        int recFind(int a, int b, ll v, int i, int ia, int ib) {
            if (seg[i] > v) return b;
            if (b <= ia || ib <= a) return b;
            if (ib == ia + 1) return ia;

            push(i);
            int im = (ia + ib) >> 1;
            int off = recFind(a, b, v, 2*i, ia, im);
            if (off < b) return off;
            else return recFind(a, b, v, 2*i+1, im, ib);
        }
    public:
        SegTree(int n) {
            while(h < n) h *= 2;
            seg.resize(2*h, 0);
            tag.resize(h, 0);
        }
        ll rangeMin(int a, int b) { return recGet(a, b+1, 1, 0, h); }
        void rangeAdd(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
        int findNext(int a, int b, ll v) { return recFind(a, b+1, v, 1, 0, h); }
};

struct SegTreeBeats {
private:
    struct Node {
        ll val;       // current value at this node (already capped locally)
        ll lazyAdd;   // pending "+=" to push to children
        ll lazyCap;   // pending "cap = min(cap, ...)" to push to children
        Node(): val(0), lazyAdd(0), lazyCap(INF) {}
    };

    static constexpr ll INF = 4 * (ll)1e18;

    int n;
    std::vector<Node> st;

    // Apply node's pending tags to itself, then push to children
    inline void pass(int head, int l, int r) {
        // 1) apply to current node
        if (st[head].lazyAdd != 0 || st[head].lazyCap != INF) {
            st[head].val = std::min(st[head].val + st[head].lazyAdd, st[head].lazyCap);

            // 2) propagate to children
            if (l != r) {
                int L = head << 1, R = L | 1;
                st[L].lazyAdd += st[head].lazyAdd;
                st[R].lazyAdd += st[head].lazyAdd;
                st[L].lazyCap = std::min(st[L].lazyCap, st[head].lazyCap);
                st[R].lazyCap = std::min(st[R].lazyCap, st[head].lazyCap);
            }

            // 3) clear tags here
            st[head].lazyAdd = 0;
            st[head].lazyCap = INF;
        }
    }

    // range add on [ql, qr) with “pure add” (cap = +INF)
    void recAdd(int head, int l, int r, int ql, int qr, ll v) {
        pass(head, l, r);
        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            st[head].lazyAdd += v;        // queue the add
            pass(head, l, r);             // apply to current node (your style)
            return;
        }
        int mid = (l + r) >> 1;
        recAdd(head << 1,     l, mid, ql, qr, v);
        recAdd(head << 1 | 1, mid + 1, r, ql, qr, v);
        // parent.val is not a merge; queries read exact node on coverage
        // (like original beats version which returns node.cap directly)
        // So no pull needed here.
    }

    // query max/cap on [ql, qr) — identical to original logic
    ll recMax(int head, int l, int r, int ql, int qr) {
        pass(head, l, r);
        if (r < ql || qr < l) return -INF;
        if (ql <= l && r <= qr) return st[head].val;
        int mid = (l + r) >> 1;
        return std::max(recMax(head << 1,     l, mid, ql, qr),
                        recMax(head << 1 | 1, mid + 1, r, ql, qr));
    }

    // apply a global ceiling C at the root (like original apply(1,0,C))
    inline void applyRootCap(ll C) {
        st[1].lazyCap = std::min(st[1].lazyCap, C);
        pass(1, 0, n - 1);
    }

public:
    // build with all zeros (same as the original beats sample)
    explicit SegTreeBeats(int n): n(n) {
        st.assign(4 * n + 5, Node());
    }

    // add v to [a, b] inclusive; then cap the whole structure by 0 at the root
    // (exactly like original: rangeAdd(...) ; apply(1,0,0))
    void rangeAdd(int a, int b, ll v) {
        recAdd(1, 0, n - 1, a, b, v);
        applyRootCap(0); // keep the original behavior: get(i) = min(A[i], 0)
    }

    // returns point value at i (min(A[i], current root cap))
    ll get(int i) {
        return recMax(1, 0, n - 1, i, i);
    }
};

const string name = "test";

int main() {
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    SegTreeBeats cur(n);
    Fenwick tot(n+1);

    vector<int> res;
    vector<vector<pair<ll, int>>> qs(n);
    vector<array<ll, 5>> ops(q);

    for (int qi = 0; qi < q; ++qi) {
        cin >> ops[qi][0];

        ll a, b;
        cin >> a >> b;
        --a; --b;
        ops[qi][1] = a; ops[qi][2] = b;

        if (ops[qi][0] == 1) {
            ll c, k;
            cin >> c >> k;
            ops[qi][3] = c; ops[qi][4] = k;

            cur.rangeAdd(a, b, -k);
            tot.add(a, k);
            tot.add(b+1, -k);

        } else if (ops[qi][0] == 2) {
            ll k;
            cin >> k;
            ops[qi][3] = k;

            cur.rangeAdd(a, b, k);

        } else if (ops[qi][0] == 3) {
            ++b;
            ll v = -cur.get(a);

            int ind = res.size();
            res.emplace_back(0);
            if (v >= b) qs[a].emplace_back(tot.get(a) - (v - b), ind);
//            cout << v << ' ' << tot.get(a) - (v - b) << '\n';
        }

    }

    const ll INF = 1e18;
    SegTree groups(n);
    vector<int> inds(n, 0);
    for (int i = 0; i < n; ++i) {
        if (qs[i].empty()) {
            groups.rangeAdd(i, i, INF);
        } else {
            sort(qs[i].begin(), qs[i].end());
            groups.rangeAdd(i, i, qs[i][0].first);
        }
    }

    for (int qi = 0; qi < q; ++qi) {
        int t = ops[qi][0];
        if (t == 1) {
            ll a = ops[qi][1]; ll b = ops[qi][2];
            ll c = ops[qi][3]; ll k = ops[qi][4];

            groups.rangeAdd(a, b, -k);
            while(true) {
                int j = groups.findNext(0, n-1, 0);
                if (j == n) break;

                res[qs[j][inds[j]].second] = c;
                ++inds[j];
                if (inds[j] >= qs[j].size()) {
                    groups.rangeAdd(j, j, INF);
                } else {
                    groups.rangeAdd(j, j, qs[j][inds[j]].first - qs[j][inds[j] - 1].first);
                }
            }
        }
    }

    for (auto c : res) cout << c << '\n';
}

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

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11