Submission #441562

#	Time	Username	Problem	Language	Result	Execution time	Memory
441562		SorahISA	Distributing Candies (IOI21_candies)	C++17	29 / 100	1099 ms	19120 KiB

candies

#include "candies.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1 << 18;

struct SegmentTree {
    int tag, val, last_change; /// tag is for range modify, val has no use if is not leaf
    char last_type;
    
    SegmentTree() {tag = 1, last_change = 0, last_type = 'E';}
};

SegmentTree seg[maxn*2];
vector<pii> C;
vector<int> V, pre_V;

void PushTag(int idx) {
    if (seg[idx].tag == 1) return;
    seg[idx<<1].tag = seg[idx<<1|1].tag = seg[idx].tag;
    if (seg[idx].tag ==  0) seg[idx<<1].last_type = seg[idx<<1|1].last_type = 'E';
    if (seg[idx].tag == -1) seg[idx<<1].last_type = seg[idx<<1|1].last_type = 'F';
    seg[idx<<1].last_change = seg[idx<<1|1].last_change = seg[idx].last_change;
    seg[idx].tag = 1;
}

int CheckVal(int idx, int qID) {
    deque<int> stk;
    int goal = idx + maxn;
    while (goal > 1) stk.eb(goal >>= 1);
    while (!stk.empty()) PushTag(stk.back()), stk.pb();
    goal = idx + maxn;
    /// pre_V[qID+1] - pre_V[last_change] ///
    // cout << seg[goal].last_type << " " << seg[goal].last_change << ": ";
    if (seg[goal].last_type == 'E') return pre_V[qID] - pre_V[seg[goal].last_change];
    if (seg[goal].last_type == 'F') return pre_V[qID] - pre_V[seg[goal].last_change] + C[idx].X;
}

void PointModify(int qX, int val, int now = 1, int nL = 0, int nR = maxn-1) {
    if (nL == nR) return seg[now].val = val, void();
    PushTag(now);
    int nM = nL + nR >> 1;
    if (qX <= nM) PointModify(qX, val, now<<1,   nL,   nM);
    else          PointModify(qX, val, now<<1|1, nM+1, nR);
}

void RangeModify(int qL, int qR, int val, int qID, int now = 1, int nL = 0, int nR = maxn-1) {
    if (qL <= nL and nR <= qR) {
        seg[now].tag = seg[now].val = val;
        seg[now].last_change = qID;
        seg[now].last_type = val == 0 ? 'E' : 'F';
        return;
    }
    if (qR < nL or nR < qL) return;
    PushTag(now);
    int nM = nL + nR >> 1;
    RangeModify(qL, qR, val, qID, now<<1,   nL,   nM);
    RangeModify(qL, qR, val, qID, now<<1|1, nM+1, nR);
}

} /// end of namespace

vector<int> distribute_candies(vector<int> _C, vector<int> L, vector<int> R, vector<int> _V) {
    C.eb(0, -1), V.eb(0);
    int N = _C.size(), Q = _V.size();
    for (int i = 0; i < N; ++i) C.eb(_C[i], i);
    for (auto &x : _V) V.eb(x);
    pre_V.assign(Q+1, 0), partial_sum(ALL(V), begin(pre_V));
    sort(ALL(C));
    
    for (int i = 1; i <= Q; ++i) {
        // cout << "\n======\n";
        // for (int j = 0; j <= N; ++j) cout << CheckVal(j, i-1) << "\n";
        // cout << "======\n";
        int lo = 0, hi = N, mi;
        if (V[i] > 0) {
            /// nothing or full ///
            if (CheckVal(N, i-1) + V[i] >= C[N].X) {
                RangeModify(0, N, -1, i); continue;
            }
            while (lo < hi) {
                mi = lo + hi >> 1;
                if (CheckVal(mi, i-1) + V[i] >= C[mi].X) lo = mi + 1; /// [0, mi] is full
                else hi = mi;                                         /// [mi, N] is not full
            }
            /// [0, lo) is full ///
            PointModify(lo, CheckVal(lo, i-1) - CheckVal(lo-1, i-1));
            RangeModify(0, lo-1, -1, i);
        }
        else {
            /// nothing or empty ///
            if (CheckVal(N, i-1) + V[i] <= 0) {
                RangeModify(0, N, 0, i); continue;
            }
            while (lo < hi) {
                mi = lo + hi >> 1;
                if (CheckVal(mi, i-1) + V[i] <= 0) lo = mi + 1; /// [0, mi] is empty
                else hi = mi;                                   /// [mi, N] is not empty
            }
            /// [0, lo) is empty ///
            PointModify(lo, CheckVal(lo, i-1) - CheckVal(lo-1, i-1));
            RangeModify(0, lo-1, 0, i);
        }
        // cout << "\nbinary search gets " << lo << "\n";
    }
    
    vector<int> ans(N);
    for (int i = 1; i <= N; ++i) ans[C[i].Y] = CheckVal(i, Q);
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'void {anonymous}::PointModify(int, int, int, int, int)':
candies.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int nM = nL + nR >> 1;
      |              ~~~^~~~
candies.cpp: In function 'void {anonymous}::RangeModify(int, int, int, int, int, int, int)':
candies.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int nM = nL + nR >> 1;
      |              ~~~^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:103:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |                 mi = lo + hi >> 1;
      |                      ~~~^~~~
candies.cpp:117:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |                 mi = lo + hi >> 1;
      |                      ~~~^~~~
candies.cpp: In function 'int {anonymous}::CheckVal(int, int)':
candies.cpp:49:16: warning: control reaches end of non-void function [-Wreturn-type]
   49 |     deque<int> stk;
      |                ^~~

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