Submission #438295

#	Time	Username	Problem	Language	Result	Execution time	Memory
438295		victoriad	Distributing Candies (IOI21_candies)	C++17	8 / 100	650 ms	21944 KiB

candies

#include "candies.h"

#include <cmath>
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <fstream>
using namespace std;
long long int dow=1e9;
int hi(int p){
    return p<<1;
}
int hd(int p){
    return (p<<1)+1;
}
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]; 
        if(a[hd(n)]>1e9)a[hd(n)]=1e9;  
        if(a[hi(n)]>1e9)a[hi(n)]=1e9;  
        if(v[hd(n)]>1e9)v[hd(n)]=1e9; 
        if(v[hi(n)]>1e9)v[hi(n)]=1e9; 
        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;
        if(v[n]>1e9)v[n]=1e9;
        if(a[n]>1e9)a[n]=1e9;
    }
    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);
        if(a[hi(n)]+a[hd(n)]>=1e9)a[n]=1e9;
        else{
        a[n]=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 0;
    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);
        if(v1+v2>=1e9)return 1e9;
        else return 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);
   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: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33