oj.uz

Submission #1083127

# Submission time Handle Problem Language Result Execution time Memory
1083127 2024-09-02T15:54:52 Z ZeroCool Distributing Candies (IOI21_candies) C++17
0 / 100
 542 ms 30032 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 542 ms 30032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -