Submission #610896

#	Time	Username	Problem	Language	Result	Execution time	Memory
610896		Tigerpants	Distributing Candies (IOI21_candies)	C++17	100 / 100	1905 ms	81548 KiB

candies

//#include <iostream>
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pi;
typedef tuple<ll, ll, ll> t3i;
typedef tuple<ll, ll, ll, ll> t4i;
typedef tuple<ll, ll, ll, ll, ll> t5i;
typedef vector<pi> vpi;
typedef vector<t3i> vt3i;
typedef vector<t4i> vt4i;
typedef vector<t5i> vt5i;

ll inf = 1000000000000000;
vi none = {-inf, 0, inf, 0, 0};

vvi segtree_M; // max val, max index, min val, min index, update
vpi segtree_M_span; // left, right

// bug: segment tree should be sorted by time, and affect a time-period

void print_tree(ll x) {
    //cout << x << ": " << segtree_M[x][0] << " " << segtree_M[x][1] << " " << segtree_M[x][2] << " " << segtree_M[x][3] << " " << segtree_M[x][4] << endl;
    if (segtree_M_span[x].first != segtree_M_span[x].second) {
        print_tree(2 * x);
        print_tree(2 * x + 1);
    }
}

vi combine(vi a, vi b) { // if they are equal, second parameter gets dips on index
    vi result(5);
    if (a[0] > b[0]) {
        result[0] = a[0]; result[1] = a[1];
    } else {
        result[0] = b[0]; result[1] = b[1];
    }
    if (a[2] < b[2]) {
        result[2] = a[2]; result[3] = a[3];
    } else {
        result[2] = b[2]; result[3] = b[3];
    }
    return result;
}

void build(ll x, ll l, ll r) {
    segtree_M_span[x] = make_pair(l, r);
    segtree_M[x] = {0, l, 0, l, 0};

    if (l == r) {
        return;
    }

    ll mid = (l + r) / 2;

    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
}

void lazy_propagation(ll x) {
    // lazy propagation for guaranteed O(log n) for updates
    // check if node has children, if so propagate down...
    if (segtree_M_span[x].first != segtree_M_span[x].second) {
        // left child
        segtree_M[2 * x][0] += segtree_M[x][4];
        segtree_M[2 * x][2] += segtree_M[x][4];
        segtree_M[2 * x][4] += segtree_M[x][4];
        // right child
        segtree_M[2 * x + 1][0] += segtree_M[x][4];
        segtree_M[2 * x + 1][2] += segtree_M[x][4];
        segtree_M[2 * x + 1][4] += segtree_M[x][4];
    }
    segtree_M[x][4] = 0;
}

void update(ll x, ll l, ll r, ll v) { // range update add v to elements of [l, r]
    lazy_propagation(x);

    if ((segtree_M_span[x].first > r) || (segtree_M_span[x].second < l)) {
        return;
    }
    if ((segtree_M_span[x].first >= l) && (segtree_M_span[x].second <= r)) {
        //cout << segtree_M_span[x].first << " " << segtree_M_span[x].second << " : " << v << endl;
        segtree_M[x][0] += v;
        segtree_M[x][2] += v;
        segtree_M[x][4] += v;
        return;
    }
    update(2 * x, l, r, v);
    update(2 * x + 1, l, r, v);
    segtree_M[x] = combine(segtree_M[2 * x], segtree_M[2 * x + 1]);
}

/*
vi query(ll x, ll l, ll r) {
    lazy_propagation(x);

    if ((segtree_M_span[x].first > r) || (segtree_M_span[x].second < l)) {
        return none;
    }
    if ((segtree_M_span[x].first >= l) && (segtree_M_span[x].second <= r)) {
        return segtree_M[x];
    }

    return combine(query(2 * x, l, r), query(2 * x + 1, l, r));
}
*/

vi binary_search_res(5);

void binary_search(ll x, ll c) {
    if (segtree_M_span[x].first == segtree_M_span[x].second) {
        if (binary_search_res[0] - binary_search_res[2] < c) {
            binary_search_res = combine(segtree_M[x], binary_search_res);
        }
        return;
    }

    lazy_propagation(x);

    vi right_res = combine(segtree_M[2 * x + 1], binary_search_res);
    if (right_res[0] - right_res[2] < c) {
        binary_search_res = right_res;
        binary_search(2 * x, c);
    } else {
        binary_search(2 * x + 1, c);
    }

    return;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    ll n = c.size();
    ll q = l.size(); // size of r and v too

    std::vector<int> result(n);

    vvi queries1(q, vi(4)); // use get<2>(queries[i]) and queries[i] = make_tuple(..., ..., ...)
    vvi queries2(q, vi(4));
    for (ll i = 0; i < q; i++) {
        queries1[i] = {(ll)l[i], (ll)r[i], (ll)v[i], i + 2};
        queries2[i] = {(ll)r[i], (ll)l[i], (ll)v[i], i + 2};
    }

    sort(queries1.begin(), queries1.end());
    sort(queries2.begin(), queries2.end());

    //cout << "sorted" << endl;

    segtree_M.resize(524288); //segtree_M.resize(4 * q + 8);
    segtree_M_span.resize(524288); //segtree_M_span.resize(4 * q + 8);
    build(1, 0, q + 1);
    update(1, 0, 0, inf);

    //print_tree(1);
    //cout << "built" << endl;

    vvi::iterator itr1 = queries1.begin(); // activation ptr
    vvi::iterator itr2 = queries2.begin(); // deactivation ptr

    ll end_sum = 0;

    for (int i = 0; i < n; i++) {
        //cout << i << "/" << n << endl;
        // activate queries
        if (itr1 != queries1.end()) {
            while (itr1->at(0) <= i) {
                update(1, itr1->at(3), q + 1, itr1->at(2));
                end_sum += itr1->at(2);
                //cout << get<0>(*itr1) << " " << get<1>(*itr1) << " " << get<2>(*itr1) << " " << get<3>(*itr1) << endl;
                //print_tree(1);
                itr1++;
                if (itr1 == queries1.end()) {
                    break;
                }
            }
        }
        //cout << "activated" << endl;
        // deactivate queries
        if (itr2 != queries2.end()) {
            while (itr2->at(0) < i) {
                update(1, itr2->at(3), q + 1, -itr2->at(2));
                end_sum -= itr2->at(2);
                //cout << get<1>(*itr2) << " " << get<0>(*itr2) << " " << get<2>(*itr2) << " " << get<3>(*itr2) << endl;
                itr2++;
                if (itr2 == queries2.end()) {
                    break;
                }
            }
        }
        //cout << "deactivated" << endl;
        //print_tree(1);
        //cout << "printed tree" << endl;
        // binary search for max - min ≈ c[i]
        //ll minj = 0;
        //ll maxj = q + 2;
        // store end result outside scope for finishing calculations

        /*
        vi q_res;
        while (minj + 1 < maxj) {
            ll midj = (minj + maxj) / 2;
            q_res = query(1, midj, q + 1);
            //cout << minj << " " << maxj << " " << midj << endl;
            //cout << q_res[0] << " " << q_res[1] << " " << q_res[2] << " " << q_res[3] << " " << q_res[4] << endl;
            if (q_res[0] - q_res[2] < (ll)c[i]) {
                maxj = midj;
            } else {
                minj = midj;
            }
        }
        q_res = query(1, minj, q + 1);
        */

        binary_search_res = none;
        binary_search(1, c[i]);
        
        //cout << minj << endl;
        //cout << q_res[0] << " " << q_res[1] << " " << q_res[2] << " " << q_res[3] << " " << q_res[4] << endl;
        //cout << "found result" << endl;
        // calculate result
        if (binary_search_res[1] > binary_search_res[3]) {
            // use q_res[1] as reference
            result[i] = c[i] + (int)(end_sum - binary_search_res[0]);
        } else {
            // use q_res[3] as reference
            result[i] = (int)(end_sum - binary_search_res[2]);
        }
        //cout << "calculated result: " << result[i] << endl;
    }

    return result;
}

/*
int main() {
    std::vector<int> c = {10, 15, 13};
    std::vector<int> l = {0, 0, 1, 0};
    std::vector<int> r = {2, 1, 2, 2};
    std::vector<int> v = {20, -11, -3, 4};
    std::vector<int> result = distribute_candies(c, l, r, v);
    for (ll i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}
*/

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