Submission #1083127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083127		ZeroCool	Distributing Candies (IOI21_candies)	C++17	0 / 100	542 ms	30032 KiB

candies

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

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

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

    void push(int k,int tl,int 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(int k,int tl,int tr,int l,int r,int v){
        push(k, tl, tr);
        if(tl > r || l > tr)return;
        if(l <= tl && tr <= r){
            lz[k] += v;
            push(k, tl, tr);
            return;
        }
        int 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]);
    }

    int qry(int k,int tl,int tr,int v){
        push(k, tl, tr);
        if(tl == tr)return mn[k];
        int 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<signed> distribute_candies(vector<signed> C, vector<signed> L,vector<signed> R, vector<signed> V) {
    int n = C.size(), q = L.size();
    vector<int> be[n], en[n];
    for(int i = 0;i < q;i++){
        be[L[i]].push_back(i);
        en[R[i]].push_back(i);
    }
    vector<signed> res(n);
    for(int i = 0;i < n;i++){
        for(auto j: be[i])seggy::upd(1, 0, q - 1, 0, j, V[j]);
       // cout<<i<<endl;

        int lo = 1, hi = C[i] + 1;
        int ans;
        while(lo <= hi){
            int tm = (lo + hi) / 2;
            int mn = 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:69:22: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |         res[i] = ans - 1;
      |                  ~~~~^~~

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