제출 #1241962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241962		hayford08	사탕 분배 (IOI21_candies)	C++20	컴파일 에러	0 ms	0 KiB

candies

#include <vector>
#include <algorithm>
using namespace std;


const int INF = 1e9;

struct SegBeats {
    struct Node {
        int mx, sx, cnt_mx;
        int mn, sn, cnt_mn;
        long long sum;
        long long add;
    };
    int n;
    vector<Node> st;
    
    SegBeats(int _n): n(_n), st(4*n) {
        build(1, 0, n-1);
    }

    void build(int p, int L, int R) {
        auto &nd = st[p];
        nd.add = 0;
        nd.sum = 0;
        nd.mx = nd.mn = 0;
        nd.sx = -INF; nd.sn = INF;
        nd.cnt_mx = nd.cnt_mn = R-L+1;
        if (L==R) return;
        int M=(L+R)/2;
        build(p<<1, L, M);
        build(p<<1|1, M+1, R);
    }

    // push down lazy tags and chmin/chmax constraints
    void push(int p, int L, int R) {
        // apply pending add
        if (st[p].add) apply_add(p<<1, st[p].add);
        if (st[p].add) apply_add(p<<1|1, st[p].add);
        st[p].add = 0;
        // push down a chmin if current mx < child mx
        push_chmin(p<<1, st[p].mx);
        push_chmin(p<<1|1, st[p].mx);
        // push down a chmax if current mn > child mn
        push_chmax(p<<1, st[p].mn);
        push_chmax(p<<1|1, st[p].mn);
    }

    // apply range_add to node p
    void apply_add(int p, long long v) {
        auto &nd = st[p];
        nd.mx += v; nd.mn += v;
        if (nd.sx != -INF) nd.sx += v;
        if (nd.sn != INF) nd.sn += v;
        nd.sum += v * (nd.cnt_mx + (nd.sum - nd.mx * nd.cnt_mx) / (nd.mn)); 
        nd.add += v;
    }

    // apply chmin(x) to node p if needed
    void push_chmin(int p, int x) {
        auto &nd = st[p];
        if (nd.mx <= x) return;
        nd.sum -= 1LL*(nd.mx - x)*nd.cnt_mx;
        nd.mx = x;
        // if the new mx equals the second max, we may need to adjust sx/cnt
        if (nd.mx == nd.sx) {
            nd.sx = -INF;
            nd.cnt_mx += /*cnt of old sx*/;
        }
        // same logic for minima side if needed...
    }

    // apply chmax(x) similarly
    void push_chmax(int p, int x) { /* mirror of chmin */ }

    // pull up from children
    void pull(int p) {
        auto &nd = st[p];
        auto &L = st[p<<1], &R = st[p<<1|1];
        // update sum
        nd.sum = L.sum + R.sum;
        // update mx, cnt_mx, sx
        if (L.mx > R.mx) {
            nd.mx = L.mx; nd.cnt_mx = L.cnt_mx;
            nd.sx = max(L.sx, R.mx);
        } else if (R.mx > L.mx) {
            nd.mx = R.mx; nd.cnt_mx = R.cnt_mx;
            nd.sx = max(R.sx, L.mx);
        } else { // equal
            nd.mx = L.mx;
            nd.cnt_mx = L.cnt_mx + R.cnt_mx;
            nd.sx = max(L.sx, R.sx);
        }
        // update mn, cnt_mn, sn similarly...
    }

    // range add
    void range_add(int i, int j, int v) { upd_add(1,0,n-1,i,j,v); }
    void upd_add(int p, int L, int R, int i, int j, int v) {
        if (j< L || R< i) return;
        if (i <= L && R <= j) { apply_add(p, v); return; }
        push(p, L, R);
        int M=(L+R)/2;
        upd_add(p<<1, L, M, i, j, v);
        upd_add(p<<1|1, M+1, R, i, j, v);
        pull(p);
    }

    // range chmin
    void range_chmin(int i, int j, int x) { upd_chmin(1,0,n-1,i,j,x); }
    void upd_chmin(int p, int L, int R, int i, int j, int x) {
        if (j< L || R< i || st[p].mx <= x) return;
        if (i <= L && R <= j && st[p].sx < x) {
            push_chmin(p, x);
            return;
        }
        push(p, L, R);
        int M=(L+R)/2;
        upd_chmin(p<<1, L, M, i, j, x);
        upd_chmin(p<<1|1, M+1, R, i, j, x);
        pull(p);
    }

    // range chmax (mirror)
    void range_chmax(int i, int j, int x) { /* … */ }

    // finally, collect all leaves
    void collect(int p, int L, int R, vector<int>& out) {
        if (L==R) {
            out[L] = st[p].mx;  // == st[p].mn == final value
            return;
        }
        push(p, L, R);
        int M=(L+R)/2;
        collect(p<<1,   L,   M, out);
        collect(p<<1|1, M+1, R, out);
    }
};

// Usage:
vector<int> distribute_candies(
    const vector<int>& c,
    const vector<int>& l,
    const vector<int>& r,
    const vector<int>& v
) {
    int n = c.size(), q = l.size();
    int C = c[0];  // all capacities are the same
    SegBeats seg(n);
    for (int j = 0; j < q; j++) {
        if (v[j] > 0) {
            seg.range_add(l[j], r[j], v[j]);
            seg.range_chmin(l[j], r[j], C);
        } else {
            seg.range_add(l[j], r[j], v[j]);
            seg.range_chmax(l[j], r[j], 0);
        }
    }
    vector<int> ans(n);
    seg.collect(1, 0, n-1, ans);
    return ans;
}

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

candies.cpp: In member function 'void SegBeats::push_chmin(int, int)':
candies.cpp:68:43: error: expected primary-expression before ';' token
   68 |             nd.cnt_mx += /*cnt of old sx*/;
      |                                           ^