Submission #831752

#	Time	Username	Problem	Language	Result	Execution time	Memory
831752		andrey27_sm	Distributing Candies (IOI21_candies)	C++17	0 / 100	198 ms	24296 KiB

candies

#include <bits/stdc++.h>
using namespace std;
int mod[800001];
int mx[800001];
int mx2[800001];
int mn[800001];
int mn2[800001];
int C;
void push_sum(int v){
    mx2[v<<1]+=mod[v];
    mx[v<<1]+= mod[v];
    mn2[v<<1]+=mod[v];
    mn[v<<1]+= mod[v];
    mod[v<<1]+=mod[v];
    mx2[v<<1|1]+=mod[v];
    mx[v<<1|1]+= mod[v];
    mn2[v<<1|1]+=mod[v];
    mn[v<<1|1]+= mod[v];
    mod[v<<1|1]+=mod[v];
    mod[v] = 0;
}
void push_min_max(int v){
    mx[v<<1] = min(mx[v],mx[v<<1]);
    mn[v<<1] = min(mx[v],mn[v<<1]);

    mx[v<<1|1] = min(mx[v],mx[v<<1|1]);
    mn[v<<1|1] = min(mx[v],mn[v<<1|1]);



    mx[v<<1] = max(mn[v],mx[v<<1]);
    mn[v<<1] = max(mn[v],mn[v<<1]);

    mx[v<<1|1] = max(mn[v],mx[v<<1|1]);
    mn[v<<1|1] = max(mn[v],mn[v<<1|1]);

}
void pull(int v){
    if(mx[v<<1] == mx[v<<1|1]){
        mx[v] = mx[v<<1];
        mx2[v] = max(mx2[v<<1],mx2[v<<1|1]);
    }
    else if(mx[v<<1] < mx[v<<1|1]){
        mx[v] = mx[v<<1|1];
        mx2[v] = max(mx[v<<1],mx2[v<<1|1]);
    }
    else{
        mx[v] = mx[v<<1];
        mx2[v] = max(mx2[v<<1],mx[v<<1|1]);
    }


    if(mn[v<<1] == mn[v<<1|1]){
        mn[v] = mn[v<<1];
        mn2[v] = min(mn2[v<<1],mn2[v<<1|1]);
    }
    else if(mn[v<<1] > mn[v<<1|1]){
        mn[v] = mn[v<<1|1];
        mn2[v] = min(mn[v<<1],mn2[v<<1|1]);
    }
    else{
        mn[v] = mn[v<<1];
        mn2[v] = min(mn2[v<<1],mn[v<<1|1]);
    }
}
void push(int v){
    push_sum(v);
    //push_min_max(v);
}
void update_add(int v,int l,int r,int tl,int tr,int val){
    if(r < tl or tr < l) return;
    if(tl <= l and r <= tr){
        mx[v]+=val;
        mx2[v]+=val;
        mn2[v]+=val;
        mn[v]+=val;
        mod[v]+=val;
        return;
    }
    push(v);
    int m = (l+r)/2;
    update_add(v<<1,l,m,tl,tr,val);
    update_add(v<<1|1,m+1,r,tl,tr,val);
    //pull(v);
}

void update_max(int v,int l,int r){
    if(mx[v] <= C) return;
    if(mx[v] > C and mx2[v] < C){
        mx[v] = C;
        mn2[v] = min(mn2[v],C);
        mn[v] = min(mn[v],C);
        return;
    }
    push(v);
    int m = (l+r)/2;
    update_max(v<<1,l,m);
    update_max(v<<1|1,m+1,r);
    pull(v);
}
void update_min(int v,int l,int r){
    if(mn[v] >= 0) return;
    if(mn[v] < 0 and mn2[v] > 0){
        mn[v] = 0;
        mx2[v] = max(mx2[v],0);
        mx[v] = max(mx[v],0);
        return;
    }
    push(v);
    int m = (l+r)/2;
    update_min(v<<1,l,m);
    update_min(v<<1|1,m+1,r);
    pull(v);
}
vector<int> blds(int v,int l,int r){
    if(l == r){
        return {mx[v]};
    }
    push(v);
    int m = (l+r)/2;
    vector<int> a = blds(v<<1,l,m);
    vector<int> b = blds(v<<1|1,m+1,r);
    for(auto e:b) a.push_back(e);
    return a;
}
vector<int> distribute_candies(vector<int> C_, vector<int> L, vector<int> R, vector<int> V) {
    C = 1e9;
    int n = C_.size();
    for (int i = 0; i < 4*n; ++i)
    {
        mod[i] = 0;
        
    }
    for (int i = 0; i < L.size(); ++i)
    {
        update_add(1,0,n-1,L[i],R[i],V[i]);
        //vector<int> tmp = blds(1,0,n-1);
        //for(int j = 0; j < 4*n;j++) cout << mn[j] << " ";
        //cout << "\n";
    }
    vector<int> tmp = blds(1,0,n-1);
    for(int i = 0;i < n;i++) tmp[i] = min(tmp[i],C_[i]);
    return tmp;
}

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:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < L.size(); ++i)
      |                     ~~^~~~~~~~~~

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