제출 #1307290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307290		opeleklanos	사탕 분배 (IOI21_candies)	C++20	0 / 100	103 ms	10404 KiB

candies

#include <iostream>
#include <vector>
#include <algorithm>
#include "candies.h"
using namespace std;

int n;
vector<int> segTree;
vector<int> s;

void update(int indx, int l, int r, int a, int b, int x){
    if(a<=l && r<=b){
        segTree[indx] += x;
        return;
    }
    int mid = (l+r)/2;
    if(a<=mid) update(indx*2+1, l, mid, a, min(mid, b), x);
    if(b>mid) update(indx*2+2, mid+1, r, max(mid+1, a), b, x);
}

void buildS(int indx, int l, int r){
    if(l == r && l<n && l>=0){
        s[l] = segTree[indx];
        return;
    }
    int mid = (l+r)/2;
    segTree[indx*2+1] += segTree[indx];
    segTree[indx*2+2] += segTree[indx];
    segTree[indx] = -1;
    buildS(indx*2+1, l, mid);
    buildS(indx*2+2, mid+1, r);
    return;
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    s.assign(c.size(), 0);
    n = c.size();
    segTree.assign(n*3, 0);
    for(int i = 0; i<l.size(); i++){
        update(0, 0, n-1, l[i], r[i], v[i]);
    }
    buildS(0, 0, n-1);
    for(int i = 0; i<n; i++) s[i] = min(s[i], c[i]);
    return s;
}

// int main(void){
//     freopen("input.txt", "r", stdin);
//     int ni, qu;
//     cin>>ni>>qu;
//     vector<int> c1(ni), l1(qu), r1(qu), v1(qu);
//     for(int i = 0; i<ni; i++) cin>>c1[i];
//     for(int i = 0; i<qu; i++) cin>>l1[i]>>r1[i]>>v1[i];
//     // for(int i = 0; i<qu; i++) cin>>r1[i];
//     // for(int i = 0; i<qu; i++) cin>>v1[i];
//     distribute_candies(c1, l1, r1, v1);
// }

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