Submission #963611

#	Time	Username	Problem	Language	Result	Execution time	Memory
963611		alontanay	Distributing Candies (IOI21_candies)	C++17	100 / 100	468 ms	55632 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"
#define f first
#define s second
// #define DEBUGGING

#ifdef DEBUGGING
#define dout(msg) cout << msg
#else
#define dout(msg) 
#endif

using namespace std;
using ll = long long;
using pli = pair<ll,int>;

const ll INF_LL = 1e18;
const ll INF = 1e9+2;


string str(ll x) {
    return to_string(x);
}
string str(bool x) {
    return to_string(x);
}
string str(int x) {
    return to_string(x);
}

template<typename X, typename Y>
string str(pair<X,Y> p) {
    return "{" + str(p.f) + ", " + str(p.s) + "}";
}

struct Seg {
    ll segSum;
    pli maxSuf, minSuf;
    int l, r, mid;
    Seg *ls, *rs;
    Seg(int l, int r): l(l), r(r), mid((l+r)/2), segSum(0), maxSuf({0,r}), minSuf({0,-r}) {
        if(l + 1 < r) {
            ls = new Seg(l, mid);
            rs = new Seg(mid, r);
        }
    }
    void update(int i, int x) {
        if(l + 1 == r) {
            segSum = x;
            maxSuf = max(pli{x,l},pli{0,r});
            minSuf = min(pli{x,-l},pli{0,-r});
            return;
        }
        (i < mid ? ls : rs)->update(i,x);
        segSum = ls->segSum + rs->segSum;
        maxSuf = max(rs->maxSuf, pli{ls->maxSuf.f+rs->segSum,ls->maxSuf.s});
        minSuf = min(rs->minSuf, pli{ls->minSuf.f+rs->segSum,ls->minSuf.s});
    }
    ll sumSuffix(int i) {
        if(l + 1 == r) {
            return i < r ? segSum : 0LL;
        }
        if(i < mid) {
            return ls->sumSuffix(i) + rs->segSum;
        }
        return rs->sumSuffix(i);
    }
    pair<ll,bool> findLastBound(ll c, pli mx, pli mn, ll sumr) {
        if(l + 1 == r) {
            return segSum < 0 ? pair<ll,bool>{mx.s,false} : pair<ll,bool>{-mn.s,true};
        }
        pli rmx = max(mx, {rs->maxSuf.f + sumr, rs->maxSuf.s});
        pli rmn = min(mn, {rs->minSuf.f + sumr, rs->minSuf.s});
        dout(str(mx) << ' ' << str(mn) << " | " << str(rmx) << ' ' << str(rmn) << endl);
        dout("   " << rmx.f - rmn.f << " >= " << c << endl);
        if(rmx.f - rmn.f >= c) {
            return rs->findLastBound(c, mx, mn, sumr);
        }
        return ls->findLastBound(c, rmx, rmn, sumr + rs->segSum);
    }
    pair<ll,bool> findLastBound(ll c) {
        return findLastBound(c, pli{0,r}, pli{0,-r},0);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    Seg seg(0, q+1);
    seg.update(0,-INF);
    vector<vector<int>> upds(n+1);
    for(int qi = 0; qi < q; qi ++) {
        upds[l[qi]].push_back(qi);
        upds[r[qi]+1].push_back(qi+q);
    }
    vector<int> res(n);
    for(int i = 0; i < n; i ++) {
        for(int upd : upds[i]) {
            int x, y;
            if(upd >= q) {
                x = upd-q+1;
                y = 0;
                seg.update(upd-q+1,0);
            } else {
                x = upd +1;
                y = v[upd];
                seg.update(upd+1,v[upd]);
            }
            dout("UPD " << x << ' ' << y << endl);
        }
        dout(seg.maxSuf.f << ' ' << seg.maxSuf.s << " | " << seg.minSuf.f << ' ' << seg.minSuf.s << endl);
        pair<ll,bool> lastBound = seg.findLastBound(c[i]);
        dout(lastBound.f << endl);
        res[i] = seg.sumSuffix(lastBound.f);
        if(lastBound.s) {
            res[i] += c[i];
        }
    }
    return res;
}

Compilation message (stderr)

candies.cpp: In constructor 'Seg::Seg(int, int)':
candies.cpp:39:15: warning: 'Seg::mid' will be initialized after [-Wreorder]
   39 |     int l, r, mid;
      |               ^~~
candies.cpp:37:8: warning:   'll Seg::segSum' [-Wreorder]
   37 |     ll segSum;
      |        ^~~~~~
candies.cpp:41:5: warning:   when initialized here [-Wreorder]
   41 |     Seg(int l, int r): l(l), r(r), mid((l+r)/2), segSum(0), maxSuf({0,r}), minSuf({0,-r}) {
      |     ^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:99:17: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   99 |             int x, y;
      |                 ^
candies.cpp:99:20: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   99 |             int x, y;
      |                    ^

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