oj.uz

답안 #438295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438295 2021-06-27T20:21:19 Z victoriad 사탕 분배 (IOI21_candies) C++17
8 / 100
 650 ms 21944 KB 
#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.0

# 결과 실행 시간 메모리 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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 650 ms 21944 KB Output is correct
2 Correct 642 ms 21188 KB Output is correct
3 Correct 640 ms 21144 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 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 -