Submission #1083130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083130		ZeroCool	Distributing Candies (IOI21_candies)	C++17	100 / 100	991 ms	43764 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
#define ll long long

const ll LOG = 20;
const ll N = 2e5 + 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e17;

namespace seggy{
    ll mn[4 * N], mx[4 * N], lz[4 * N];

    void push(ll k,ll tl,ll tr){
        mn[k] += lz[k], mx[k] += lz[k];
        if(tl != tr)lz[k * 2] += lz[k], lz[k *2 + 1] += lz[k];
        lz[k]  =0;
    }

    void upd(ll k,ll tl,ll tr,ll l,ll r,ll v){
        push(k, tl, tr);
        if(tl > r || l > tr)return;
        if(l <= tl && tr <= r){
            lz[k] += v;
            push(k, tl, tr);
            return;
        }
        ll tm = (tl + tr) / 2;
        upd(k *2, tl, tm, l, r, v);
        upd(k * 2 + 1, tm + 1, tr ,l, r, v);
        mn[k] = min(mn[k *2], mn[k *2 + 1]);
        mx[k] = max(mx[k * 2], mx[k *2 + 1]);
    }

    ll qry(ll k,ll tl,ll tr,ll v){
        push(k, tl, tr);
        if(tl == tr)return mn[k];
        ll tm = (tl + tr) / 2;
        if(mx[k *2 + 1] + lz[k *2 + 1]>= v)return qry(k * 2 + 1, tm + 1, tr, v);
        else return min(mn[k *2 + 1] + lz[k *2 + 1], qry(k * 2, tl, tm, v));
    }
};


vector<int> distribute_candies(vector<int> C, vector<int> L,vector<int> R, vector<int> V) {
    ll n = C.size(), q = L.size();
    vector<ll> be[n], en[n];
    for(ll i = 0;i < q;i++){
        be[L[i]].push_back(i);
        en[R[i]].push_back(i);
    }
    vector<int> res(n);
    for(ll i = 0;i < n;i++){
        for(auto j: be[i])seggy::upd(1, 0, q - 1, 0, j, V[j]);
       // cout<<i<<endl;

        ll lo = 1, hi = C[i] + 1;
        ll ans;
        while(lo <= hi){
            ll tm = (lo + hi) / 2;
            ll mn = min(0ll, seggy::qry(1, 0, q - 1, tm));
            if(seggy::mx[1] < tm)mn = -INF;
            if(tm - mn > C[i]){
                ans = tm;
                hi = tm - 1;
            }else lo = tm + 1;
        }
        res[i] = ans - 1;
        for(auto j: en[i])seggy::upd(1, 0, q - 1, 0, j, -V[j]);

    }
    return res;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:70:22: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |         res[i] = ans - 1;
      |                  ~~~~^~~

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