Submission #751485

#	Time	Username	Problem	Language	Result	Execution time	Memory
751485		Ronin13	Distributing Candies (IOI21_candies)	C++17	100 / 100	1075 ms	50840 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll,ll>
#include <vector>

/*
3
10 15 13
2
0 2 20
0 1 -11
*/

using namespace std;
const int nmax = 200001;
struct node{
    ll sum, mn, mx;
    int mni, mxi;
    node(){
        sum = 0;
        mn = 1e18;
        mx = -1e18;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    if(a.mn < a.sum + b.mn){
        c.mn = a.mn, c.mni = a.mni;
    }
    else c.mn = a.sum + b.mn, c.mni = b.mni;
    if(a.mx > a.sum + b.mx){
        c.mx = a.mx, c.mxi = a.mxi;
    }
    else c.mx = a.sum + b.mx, c.mxi = b.mxi;
    return c;
}


node get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st){
        return {};
    }
    if(l >= st && r <= fin){
        return t[v];
    }
    int m = (l + r) / 2;
    return merg(get(2 * v ,l, m, st, fin),
                get(2 * v + 1, m + 1, r, st, fin));
}

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v].mn = t[v].mx = t[v].sum = val;
        t[v].mni = t[v].mxi = l;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

ll getsum(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 0;
    if(l >= st && r <= fin)
        return t[v].sum;
    int m = (l + r) / 2;
    return getsum(2 * v, l, m, st, fin) + getsum(2 * v + 1, m + 1, r, st, fin);
}

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();
    vector <int> ans(n);
    int m = l.size();
    update(1, 1, m + 2, 1, 1e18);
    update(1, 1, m + 2, 2, -1e18);
    vector <vector <pii> > in(n + 1);
    for(int i = 0; i < m; i++){
        in[l[i]].pb({v[i], i + 3});
        in[r[i] + 1].pb({0, i + 3});
    }
    for(int i = 0; i < n; i++){
        for(auto to : in[i]){
            update(1, 1, m + 2, to.s, to.f);
        }
        int l = 0, r = m + 3;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            node x = get(1, 1, m + 2, mid, m + 2);
            if(x.mx - x.mn >= c[i]) l = mid;
            else r = mid;
        }
        //cout << l << "\n";
        node x = get(1, 1, m + 2, l, m + 2);
        if(x.mni < x.mxi){
            ans[i] = c[i] - getsum(1, 1, m + 2, 1, l - 1) - x.mx + t[1].sum;
        }
        else ans[i] = t[1].sum - getsum(1, 1, m + 2, 1, l - 1) - x.mn;
    }
    return ans;
}

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