oj.uz

답안 #831752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831752 2023-08-20T13:17:43 Z andrey27_sm 사탕 분배 (IOI21_candies) C++17
0 / 100
 198 ms 24296 KB 
#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

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.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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