제출 #710673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710673		1bin	사탕 분배 (IOI21_candies)	C++17	0 / 100	549 ms	31908 KiB

candies

#include <bits/stdc++.h>
//#include "candies.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 18;
ll n, q, lazy[b * 2];
vector<pair<int, int>> tmp[b];
pair<ll, ll> seg[b * 2];

void upd_lazy(int ix, int l, int r){
    if(!lazy[ix]) return;
    seg[ix].first += lazy[ix];
    seg[ix].second += lazy[ix];
    if(l ^ r){
            lazy[ix * 2] += lazy[ix];
            lazy[ix * 2 + 1] += lazy[ix];
    }
    lazy[ix] = 0;
    return;
}

void upd(int ix, int nl, int nr, int l, int r, ll v){
    upd_lazy(ix, nl, nr);
    if(nl > r || nr < l) return;
    if(nl >= l && nr <= r){
        lazy[ix] += v;
        upd_lazy(ix, nl, nr);
        return;
    }
    int m = (nl + nr) / 2;
    upd(ix * 2, nl, m, l, r, v);
    upd(ix * 2 + 1, m + 1, nr, l, r, v);
    seg[ix].first = min(seg[ix * 2].first, seg[ix * 2 + 1].first);
    seg[ix].second = max(seg[ix * 2].second, seg[ix * 2 + 1].second);
    return;
}

ll f(int k){
    int ix = 1, l = 0, r = b - 1, m;
    while(l < r){
        upd_lazy(1, l, r);
        m = (l + r) / 2;
        ix <<= 1;
        if(k <= m) r = m;
        else l = m + 1, ix++;
    }
    return seg[ix].first;
}

int find(ll c){
    ll ix = 1, l = 0, r = b - 1, mx = -1e18, mn = 1e18;
    upd_lazy(ix, l, r);
    while(l < r){
        int mid = (l + r) / 2;
        
        ix = ix * 2 + 1;
        upd_lazy(ix, mid + 1, r);
        ll mnn = min(mn, seg[ix].first);
        ll mxx = max(mx, seg[ix].second);
        if(mxx - mnn > c) l = mid + 1;
        else{
            ix--;
            upd_lazy(ix, l, mid);
            r = mid;
            mn = min(mn, mnn);
            mx = max(mx, mxx);
        }
    }
    ll s = f(l + 1);
    ll e = f(q);
    //cout << l + 1 << ' ' << q << ' ' << s << ' ' << e << '\n';
    if(f(l) >= s) return max(e - s, 0LL);
    return min(c - s + e, c);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<int> ans(n);
    q = l.size();
    for(int i = 0; i < q; i++){
        tmp[l[i]].emplace_back(i + 1, v[i]);
        tmp[r[i] + 1].emplace_back(i + 1, -v[i]);
    }
    
    for(int i = 0; i <= q; i++) seg[b + i] = {0, 0};
    for(int i = q + 1; i < b; i++) seg[b + i] = {1e18, -1e18};
    for(int i = b - 1; i; i--) 
        seg[i] = {min(seg[i * 2].first, seg[i * 2 + 1].first), max(seg[i * 2].second, seg[i * 2 + 1].second)};
    for(int i = 0; i < n; i++){
        //cout << "now is " << i << '\n';
        for(auto& [qi, x] : tmp[i]) upd(1, 0, b - 1, qi, q, x);//, cout << "upd " << qi << ' ' << q << ' '  << x << '\n';
        //for(int i = 0; i <= q; i++) cout << f(i) << ' ';
        //cout << '\n';
        auto[mn, mx] = seg[1];
        if(mx - mn <= c[i]) ans[i] = mx - mn;
        else ans[i] = find(c[i]);
    }
    return ans;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    vector<int> c, l, r, v;
    int n, q, x;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x, c.emplace_back(x);
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> x, l.emplace_back(x);
        cin >> x, r.emplace_back(x);    
        cin >> x, v.emplace_back(x);    
    }
    
    vector<int> ans = distribute_candies(c, l, r, v);
    for(int i = 0; i < n; i++) cout << ans[i] << ' ';
    return 0;
}*/

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