oj.uz

Submission #438169

# Submission time Handle Problem Language Result Execution time Memory
438169 2021-06-27T17:27:58 Z victoriad Distributing Candies (IOI21_candies) C++17
0 / 100
 499 ms 19876 KB 
#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.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 499 ms 19876 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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