This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define tol(bi) ((1LL)<<((int)(bi)))
struct DumduzSegTree{
vector<int> segtree;
DumduzSegTree(int n){
segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
}
void update(int tl, int tr, int v, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>=tl && r<=tr) return void(segtree[node]+=v);
if (l>tr || r<tl) return;
int mid = l+(r-l)/2;
if (tl<=mid) update(tl, tr, v, l, mid, node*2+1);
if (mid<tr) update(tl, tr, v, mid+1, r, node*2+2);
}
int query(int x){
int l = 0, r = segtree.size()/2, node = 0;
int ret = 0;
while (l<r){
ret+=segtree[node];
int mid = l+(r-l)/2;
if (x<=mid){
r=mid;
node=node*2+1;
}
else {
l=mid+1;
node=node*2+2;
}
}
return ret+segtree[node];
}
};
struct HafifDegisikSegTree{
vector<int> segtree;
int k;
HafifDegisikSegTree(int n, int k):k(k){
segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
};
void dallan(int node){
if (node*2+1<segtree.size()){
segtree[node*2+1]+=segtree[node];
segtree[node*2+2]+=segtree[node];
segtree[node*2+1]=max(0,min(k,segtree[node*2+1]));
segtree[node*2+2]=max(0,min(k,segtree[node*2+2]));
segtree[node]=0;
}
}
void update(int tl, int tr, int v, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
dallan(node);
if (l>=tl && r<=tr) return segtree[node]+=v,dallan(node);
if (l>tr || r<tl) return;
int mid = l+(r-l)/2;
if (tl<=mid) update(tl, tr, v, l, mid, node*2+1);
if (mid<tr) update(tl,tr,v,mid+1,r,node*2+2);
}
int query(int x){
int l = 0, r = segtree.size(), node = 0;
while (l<r){
int mid = l+(r-l)/2;
dallan(node);
node=node*2+1;
if (x<=mid){
r=mid;
}
else {
l=mid+1;
node++;
}
}
return segtree[node];
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
bool sub2 = true;
bool sub3 = true;
for (int i = 0; i < q; i++){
if (v[i]<0) sub2=false;
}
for (int i = 0; i < n; ++i)
{
if (c[i]!=c[0]) sub3=false;
}
if (n<=2000 && q<=2000){
vector<int> ret(n);
for (int i = 0; i < q; ++i)
{
for (int j = l[i]; j <= r[i]; j++){
ret[j]=max(0,min(c[j],ret[j]+v[i]));
}
}
return ret;
}
else if (sub2){
DumduzSegTree segtree(n);
for (int i = 0; i < q; i++){
segtree.update(l[i],r[i],v[i]);
}
vector<int> ret(n);
for (int i = 0; i < n; i++){
ret[i]=min(c[i],segtree.query(i));
}
return ret;
}
else if (sub3){
HafifDegisikSegTree segtree(n,c[0]);
for (int i = 0; i < n; ++i)
{
segtree.update(l[i],r[i],v[i]);
}
vector<int> ret(n);
for (int i = 0; i < n; ++i)
{
ret[i]=segtree.query(i);
}
return ret;
}
else {
//subtask4
return vector<int>(n,23);
}
}
Compilation message (stderr)
candies.cpp: In member function 'void HafifDegisikSegTree::dallan(int)':
candies.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if (node*2+1<segtree.size()){
| ~~~~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |