Submission #722709

#	Time	Username	Problem	Language	Result	Execution time	Memory
722709		drdilyor	Distributing Candies (IOI21_candies)	C++17	100 / 100	492 ms	48652 KiB

candies

#include<bits/stdc++.h>
#include"candies.h"
using namespace std;
using ll = long long;


struct segtree {
    struct node {
        ll s{}, mx{}, mn{};
        node operator+(const node& o) {
            return node{s + o.s, max(o.mx, o.s + mx), min(o.mn, o.s + mn)};
        }
    };
    int n;
    vector<node> t;
    segtree(int m) : n(m), t(m*4) {}
    void upd(int i, int x) {
        t[i += n] = node {x, max(0, x), min(0, x)};
        for (i /= 2; i >= 1; i /= 2)
            t[i] = t[i*2] + t[i*2+1];
    }
    node query(int l, int r) {
        node resl, resr;
        l += n; r += n;
        while (l <=r) {
            if (l%2==1) resl = resl + t[l++];
            if (r%2==0) resr = t[r--] + resr;
            l /= 2; r /= 2;
        }
        return resl + resr;
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size();
    int m = (int)v.size();

    vector<vector<int>> in(n), out(n);
    for (int i = 0; i < m; i++) {
        in[l[i]].push_back(i);
        out[r[i]].push_back(i);
    }

    segtree vcur(m);

    for(int i = 0; i < n; i ++){
        for (int j : in[i]) {
            vcur.upd(j, -v[j]);
        }

        int l = 0, r = m;
        while(l <= r){
            int mid = (l + r) >> 1;
            auto [s, mx, mn] = vcur.query(mid, m-1);
            if(mx - mn >= c[i]) {
                l = mid + 1;
            }else r = mid - 1;
        }
        r ++;
        if(r == 0 || v[r - 1] < 0){
            auto [s, mx, mn] = vcur.query(r, m-1);
            c[i] = -mn;
        }else{
            auto [s, mx, mn] = vcur.query(r, m-1);
            c[i] = c[i] - mx;
        }

        for (int j : out[i]) {
            vcur.upd(j, 0);
        }
    }
    //for(auto u : suf) cout << u << ' ';cout << endl;
    return c;
}

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