Submission #438169

#	Time	Username	Problem	Language	Result	Execution time	Memory
438169		victoriad	Distributing Candies (IOI21_candies)	C++17	0 / 100	499 ms	19876 KiB

candies

#include "candies.h"

#include <cmath>
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
long long int dow=1e9;
int hi(int p){
    return p<<1;
}
int hd(int p){
    return (p<<1)+1;
}
void build(int n,int L,int R,vector<long long int>&a,vector<int>&l){
    if(L<R){
        int m=L+(R-L)/2;
        build(hi(n),L,m,a,l);
        build(hd(n),m+1,R,a,l);
        a[n]=min(dow,a[hi(n)]+a[hd(n)]);
    }
    else{
        a[n]=l[L];
    }
}
void pop(int n,int L,int R,vector<long long int>&a,vector<long long int>&v){
    if(L!=R){
        a[hd(n)]+=v[n];
        a[hi(n)]+=v[n];    
        v[hd(n)]+=v[n];
        v[hi(n)]+=v[n];    
        v[n]=0;
    }
    else{
        v[n]=0;
    }
}
void sumar(int n,int L,int R,int st,int fi,int su,vector<long long int>&a,vector<long long int>&v){
    if(L>=st && R<=fi){
        v[n]+=su;
        a[n]+=su;
    }
    else if(st>R||fi<L)return;
    else{
        pop(n,L,R,a,v);
        int m=L+(R-L)/2;
        sumar(hi(n),L,m,st,fi,su,a,v);
        sumar(hd(n),m+1,R,st,fi,su,a,v);
        a[n]=min(dow,a[hi(n)]+a[hd(n)]);
    }
}
int valor(int n,int L,int R,int st,int fi,vector<long long int>&a,vector<long long int>&v){
    if(L>=st && R<=fi){
        pop(n,L,R,a,v);
        return a[n];
    }
    else if(st>R||fi<L)return -1e9;
    else{
        pop(n,L,R,a,v);
        int m=L+(R-L)/2;
        long long int v1=valor(hi(n),L,m,st,fi,a,v);
        long long int v2=valor(hd(n),m+1,R,st,fi,a,v);
        return min(dow,v1+v2);
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    int m=v.size();
   vector<int> s(n,0);
   vector<long long int>a(4*n,0);
   vector<long long int>va(4*n,0);
   build(1,0,n-1,a,s);
   for(int i=0;i<m;i++){
       sumar(1,0,n-1,l[i],r[i],v[i],a,va);
   }
   for(int i=0;i<n;i++){
       int x=valor(1,0,n-1,i,i,a,va);
       s[i]=min(c[i],x);
   }
    return s;
}

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