제출 #1307388

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

candies

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

#define ll long long

ll n;
vector<ll> segTree;
vector<ll> s;
ll maxCapacity;

void update(ll indx, ll l, ll r, ll a, ll b, ll x){
    if(a<=l && r<=b){
        segTree[indx] = min(maxCapacity, segTree[indx]);
        segTree[indx] = max((ll)0, segTree[indx]);
        segTree[indx] = max((ll)0, min(maxCapacity, segTree[indx] + (ll)x));
        return;
    }
    segTree[indx*2+1] = max((ll)0, min(maxCapacity, segTree[indx*2+1]+segTree[indx]));
    segTree[indx*2+2] = max((ll)0, min(maxCapacity, segTree[indx*2+2]+segTree[indx]));
    // segTree[indx*2+2] += segTree[indx];
    segTree[indx] = 0;
    ll 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(ll indx, ll l, ll r){
    segTree[indx] = min(maxCapacity, segTree[indx]);
    segTree[indx] = max((ll)0, segTree[indx]);
    if(l == r && l<n && l>=0){
        s[l] = segTree[indx];
        return;
    }
    ll mid = (l+r)/2;
    // segTree[indx*2+1] += segTree[indx];
    segTree[indx*2+1] = max((ll)0, min(maxCapacity, segTree[indx*2+1]+segTree[indx]));
    segTree[indx*2+2] = max((ll)0, min(maxCapacity, segTree[indx*2+2]+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){
    maxCapacity = c[0];
    s.assign(c.size(), 0);
    n = c.size();
    segTree.assign(n*3, 0);
    for(ll i = 0; i<l.size(); i++){
        update(0, 0, n-1, l[i], r[i], v[i]);
    }
    buildS(0, 0, n-1);
    vector<int> ans(n, 0);
    for(ll i = 0; i<n; i++) ans[i] = (int)min(s[i], (ll)c[i]);
    return ans;
}

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

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