제출 #1005761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005761		ProtonDecay314	사탕 분배 (IOI21_candies)	C++17	40 / 100	1240 ms	58292 KiB

candies

#include<bits/stdc++.h>
// #define DEBUG
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;

struct query {
    ll i;
    ll t;
    ll v;

    bool operator< (const query& o) const {
        return i < o.i;
    }
};

struct Tree {
    ll mn;
    ll mx;
    ll mn_ind;
    ll mx_ind;
    ll sum;
    ll inc;
    Tree* lt;
    Tree* rt;
    ll l, r;

    Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};

    void push() {
        if(inc == 0) return;

        if(lt == nullptr) {
            inc = 0;
            return;
        }

        lt->inc += inc;
        lt->mn += inc;
        lt->mx += inc;
        lt->sum += (lt->r - lt->l + 1) * inc;
        
        rt->inc += inc;
        rt->mn += inc;
        rt->mx += inc;
        rt->sum += (rt->r - rt->l + 1) * inc;

        inc = 0;
    }

    void combine() {
        mn = min(lt->mn, rt->mn);
        mx = max(lt->mx, rt->mx);
        if(lt->mn < rt->mn) mn_ind = lt->mn_ind;
        else mn_ind = rt->mn_ind;
        if(lt->mx > rt->mx) mx_ind = lt->mx_ind;
        else mx_ind = rt->mx_ind;
        sum = lt->sum + rt->sum;
    }

    void build() {
        if(l == r) {
            mn_ind = mx_ind = l;
            return;
        }
        ll m = (l + r) >> 1;

        lt = new Tree(l, m);
        rt = new Tree(m + 1, r);
        lt->build();
        rt->build();

        combine();
    }

    void upd(ll ql, ll qr, ll a_inc) {
        if(ql > r || qr < l) return;
        push();

        if(ql == l && qr == r) {
            inc += a_inc;
            mn += a_inc;
            mx += a_inc;
            sum += (r - l + 1) * a_inc;
            push();
            return;
        }

        ll m = (l + r) >> 1;

        lt->upd(ql, min(m, qr), a_inc);
        rt->upd(max(m + 1, ql), qr, a_inc);

        combine();
    }

    ll range_max(ll ql, ll qr) {
        if(ql > r || qr < l) return numeric_limits<ll>::min();
        push();
        if(ql == l && qr == r) return mx;
        ll m = (l + r) >> 1;
        return max(lt->range_max(ql, min(m, qr)), rt->range_max(max(m + 1, ql), qr));
    }
    pll max_with_ind(ll ql, ll qr) {
        if(ql > r || qr < l) return {-1ll, -1ll};
        push();
        if(ql == l && qr == r) return {mx_ind, mx};
        ll m = (l + r) >> 1;
        pll lind = lt->max_with_ind(ql, min(m, qr));
        pll rind = rt->max_with_ind(max(m + 1, ql), qr);
        if(lind.first == -1) return rind;
        if(rind.first == -1) return lind;
        if(lind.second > rind.second) return lind;
        return rind;
    }
    ll ind_max(ll ql, ll qr) {
        return max_with_ind(ql, qr).first;
    }

    ll range_min(ll ql, ll qr) {
        if(ql > r || qr < l) return numeric_limits<ll>::max();
        push();
        if(ql == l && qr == r) return mn;
        ll m = (l + r) >> 1;
        return min(lt->range_min(ql, min(m, qr)), rt->range_min(max(m + 1, ql), qr));
    }

    pll min_with_ind(ll ql, ll qr) {
        if(ql > r || qr < l) return {-1ll, -1ll};
        push();
        if(ql == l && qr == r) return {mn_ind, mn};
        ll m = (l + r) >> 1;
        pll lind = lt->min_with_ind(ql, min(m, qr));
        pll rind = rt->min_with_ind(max(m + 1, ql), qr);
        if(lind.first == -1) return rind;
        if(rind.first == -1) return lind;
        if(lind.second < rind.second) return lind;
        return rind;
    }

    ll ind_min(ll ql, ll qr) {
        return min_with_ind(ql, qr).first;
    }

    ll range_sum(ll ql, ll qr) {
        if(ql > r || qr < l) return 0;
        push();
        if(ql == l && qr == r) return sum;
        ll m = (l + r) >> 1;
        return lt->range_sum(ql, min(m, qr)) + rt->range_sum(max(m + 1, ql), qr);
    }
};

// IOI Function Signatures
vi distribute_candies(vi c, vi l, vi r, vi v) {
    ll n = size(c);
    ll q = size(l);

    vector<query> queries;

    for(ll i = 0; i < q; i++) {
        queries.push_back({l[i], i, v[i]});
        queries.push_back({r[i] + 1, i, -v[i]});
    } 

    sort(queries.begin(), queries.end()); // Sort by array index

    // Create a segtree of updates
    Tree tr(0, q);
    tr.build();

    // Two pointer approach to adding queries
    vi ans(n, 0);
    ll p1 = 0, p2 = 0;
    for(ll i = 0; i < n; i++) {
        while(i < n && i > queries[p1].i) p1++;
        p2 = p1;
        while(i < n && i >= queries[p2].i) p2++;

        for(ll j = p1; j < p2; j++) {
            // #ifdef DEBUG
            // cout << "ACTIVATING: " << queries[j].i << " " << queries[j].t << " " << queries[j].v << endl;
            // #endif
            tr.upd(queries[j].t + 1, q, queries[j].v);
        }

        ll l = -1, r = q + 1;
        while(r - l > 1) {
            ll m = (l + r) >> 1;
            // #ifdef DEBUG
            // cout << "MAXMIN " << m << ", " << tr.range_max(m, q - 1) << " " << tr.range_min(m, q - 1) << endl;
            // #endif
            if(tr.range_max(m, q) - tr.range_min(m, q) < c[i]) r = m;
            else l = m;
        }
        #ifdef DEBUG
        for(int j = 0; j <= q; j++) {
            cout << tr.range_sum(j, j) << " ";
        }
        cout << endl;
        #endif
        if(r == 0) {
            if(tr.range_max(r, q) >= c[i]) {
                // #ifdef DEBUG
                // cout << tr.range_sum(q, q) - tr.range_sum(0, 0) << endl;
                // #endif
                ll ind_max = tr.ind_max(r, q);
                ans[i] = max(c[i] + tr.range_sum(q, q) - tr.range_sum(ind_max, ind_max), 0ll);
            } else {
                ll ind_min = tr.ind_min(r, q);
                ans[i] = max(min(tr.range_sum(q, q) - tr.range_sum(ind_min, ind_min), (ll)c[i]), 0ll);
            }
        } else {
            #ifdef DEBUG
            cout << "BINSEARCH " << i << ", " << r << ", " << tr.range_min(l, q) << ", " << tr.range_max(l, q) << ", " << tr.range_sum(l, l) << endl;
            #endif
            ll left_elem = tr.range_sum(l, l);
            ll range_min = tr.range_min(l, q);
            ll range_max = tr.range_max(l, q);
            #ifdef DEBUG
            cout << "RANGE SUM: " << tr.range_sum(q, q) - tr.range_sum(r, r) << ", " << c[i] << endl;
            #endif
            if(left_elem == range_min) {
                ll ind_max = tr.ind_max(l, q);
                #ifdef DEBUG
                cout << "IND MAX: " << ind_max << endl;
                #endif
                ans[i] = max(tr.range_sum(q, q) - tr.range_sum(ind_max, ind_max) + c[i], 0ll);
            } else {
                ll ind_min = tr.ind_min(l, q);
                #ifdef DEBUG
                cout << "IND MIN: " << ind_min << endl;
                #endif
                ans[i] = min(tr.range_sum(q, q) - tr.range_sum(ind_min, ind_min), (ll)c[i]);
            }
        }
        // ans[i] = r;
    }

    return ans;
}

// Driver Function
#ifdef DEBUG
int main() {
    int n;
    cin >> n;
    
    vi c(n, 0);
    for(int& cv : c) {
        cin >> cv;
    }

    int q;
    cin >> q;

    vi l(q, 0), r(q, 0), v(q, 0);

    for(int i = 0; i < q ; i++) {
        cin >> l[i] >> r[i] >> v[i];
    }

    vi ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; i++) {
        cout << ans[i];
        if(i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}
#endif

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

candies.cpp: In constructor 'Tree::Tree(ll, ll)':
candies.cpp:28:11: warning: 'Tree::r' will be initialized after [-Wreorder]
   28 |     ll l, r;
      |           ^
candies.cpp:26:11: warning:   'Tree* Tree::lt' [-Wreorder]
   26 |     Tree* lt;
      |           ^~
candies.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
      |     ^~~~
candies.cpp:27:11: warning: 'Tree::rt' will be initialized after [-Wreorder]
   27 |     Tree* rt;
      |           ^~
candies.cpp:20:8: warning:   'll Tree::mn' [-Wreorder]
   20 |     ll mn;
      |        ^~
candies.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
      |     ^~~~
candies.cpp:25:8: warning: 'Tree::inc' will be initialized after [-Wreorder]
   25 |     ll inc;
      |        ^~~
candies.cpp:22:8: warning:   'll Tree::mn_ind' [-Wreorder]
   22 |     ll mn_ind;
      |        ^~~~~~
candies.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
      |     ^~~~
candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:221:16: warning: unused variable 'range_max' [-Wunused-variable]
  221 |             ll range_max = tr.range_max(l, q);
      |                ^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33