Submission #631089

#	Time	Username	Problem	Language	Result	Execution time	Memory
631089		tmncollins	Distributing Candies (IOI21_candies)	C++17	8 / 100	889 ms	49764 KiB

candies

#include "candies.h"

#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

// segment tree with both min and max storage
// min stores the minimum number of candies that are in the box at any time 
// max stores the maximum number of candies that are in the box at any time 

// the nth node in the underlying array of the segment tree stores the state of the box 
// after the nth update has been processed. 

// we process the updates in order of ranges rather than chronilogical order, allowing the 
// final value for each box to be determined one by one from left to right

vector<long long> segment_tree_sum;
vector<long long> segment_tree_min;
vector<long long> segment_tree_max;
vector<long long> lazy;

void push_lazy(long long i);

void add(long long sl, long long sr, long long l, long long r, long long v, long long i = 1) {
//    cout << sl << " => " << sr << " " << l << " => " << r << " " << v << "\n";
    
    if (sl != sr) {
//        lazy[i] += v;
        push_lazy(i);
    }

    if (sl == l && sr == r) {
        if (sl != sr) {
            lazy[i] += v;
            push_lazy(i);
        }
        else {
            segment_tree_sum[i] += v;
            segment_tree_min[i] += v;
            segment_tree_max[i] += v;
        }
        return;
    }

    long long mid = (sl + sr) / 2;
    if (l <= mid) {
        add(sl, mid, l, min(r, mid), v, i*2);
    }
    if (r > mid) {
        add(mid+1, sr, max(l, mid+1), r, v, i*2+1);
    }

    segment_tree_min[i] = min(segment_tree_min[i*2], segment_tree_min[i*2+1]);
    segment_tree_max[i] = max(segment_tree_max[i*2], segment_tree_max[i*2+1]);
    segment_tree_sum[i] = segment_tree_sum[i*2] + segment_tree_sum[i*2+1];
}

void push_lazy(long long i) {
    if (i*2 >= (long long) segment_tree_sum.size()) return;
    if (lazy[i] == 0) {
        segment_tree_min[i] = min(segment_tree_min[i*2], segment_tree_min[i*2+1]);
        segment_tree_max[i] = max(segment_tree_max[i*2], segment_tree_max[i*2+1]);
        return;
    }
    lazy[i*2] += lazy[i];
    lazy[i*2+1] += lazy[i];
    segment_tree_sum[i*2] += lazy[i];
    segment_tree_sum[i*2+1] += lazy[i];
    segment_tree_min[i*2] += lazy[i];
    segment_tree_min[i*2+1] += lazy[i];
    segment_tree_max[i*2] += lazy[i];
    segment_tree_max[i*2+1] += lazy[i];
    lazy[i] = 0;
    segment_tree_min[i] = min(segment_tree_min[i*2], segment_tree_min[i*2+1]);
    segment_tree_max[i] = max(segment_tree_max[i*2], segment_tree_max[i*2+1]);
}

vector<long long> query(long long sl, long long sr, long long l, long long r, long long i = 1) {
//    cout << i << " " << r << " " << sr << "\n";
    push_lazy(i);

    if (sl == l && sr == r) {
        return {segment_tree_sum[i], segment_tree_min[i], segment_tree_max[i]};
    }

//    push_lazy(i);

    vector<long long> ans = {0, 0, 0};

    long long mid = (sl + sr) / 2;
    if (l <= mid) {
        vector<long long> q = query(sl, mid, l, min(mid, r), i*2);
        ans[0] += q[0];
        ans[1] = min(ans[1], q[1]);
        ans[2] = max(ans[2], q[2]);
    }
    if (r > mid) {
        vector<long long> q = query(mid+1, sr, max(mid+1, l), r, i*2+1);
        ans[0] += q[0];
        ans[1] = min(ans[1], q[1]);
        ans[2] = max(ans[2], q[2]);
    }

    return ans;
}

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

    long long sr = log2(l.size()) + 1;
    sr = (1 << sr);
    long long arr_size = (sr) * 2;
    sr -= 1;

//    cout << "size : " << arr_size << "\n";

    segment_tree_sum = vector<long long> (arr_size, 0);
    segment_tree_min = vector<long long> (arr_size, 0);
    segment_tree_max = vector<long long> (arr_size, 0);
    lazy = vector<long long> (arr_size, 0);

    vector<vector<long long>> ranges;

    for (long long k = 0; k < (long long) l.size(); k++) {
        ranges.push_back({l[k], k, v[k]});
        ranges.push_back({r[k] + 1, k, -v[k]});
    }

    sort(ranges.begin(), ranges.end());

    vector<int> ans(n);
    long long ptr = 0;

    // line sweep on queries
    for (auto p : ranges) {
        long long pos = p[0], val = p[2], q = p[1];
//        cout << p[0] << " " << p[1] << " " << p[2] << " add\n";

        if (pos != ptr) {
        vector<long long> res = query(0, sr, 0, sr); // get min and max
        vector<long long> back = query(0, sr, sr, sr); // get the final value
//        cout << "res : " << res[0] << " " << res[1] << " " << res[2] << "\n";
//        cout << "back: " << back[0]<< " " << back[1]<< " " << back[2]<< "\n";

        // update boxes
        while (pos != ptr) {
//            cout << "ptr " << ptr << "\n";
            long long candies = back[0];
            long long too_many = 0, too_few = 0;
            if (res[2] > c[ptr]) {
                too_many = res[2] - c[ptr];
            }
            if (res[1] - too_many < 0) too_few = 0 - (res[1] - too_many);
//            cout << candies << " " << too_many << " " << too_few << " -p\n";
            candies += too_few - too_many;
            candies = min(candies, (long long) c[ptr]);
            candies = max((long long) 0, candies);
            ans[ptr] = candies;
            ptr++;
        }
        }

        add(0, sr, q, sr, val);

        /*
        for (long long k = 0; k < (long long) segment_tree_sum.size(); k++) cout << segment_tree_sum[k] << " ";
        cout << "\n";
        for (long long k = 0; k < (long long) segment_tree_sum.size(); k++) cout << segment_tree_min[k] << " ";
        cout << "\n";
        for (long long k = 0; k < (long long) segment_tree_sum.size(); k++) cout << segment_tree_max[k] << " ";
        cout << "\n";
        for (long long k = 0; k < (long long) segment_tree_sum.size(); k++) cout << lazy[k] << " ";
        cout << "\n";
        */
        
    }


    return ans;
}

/*
0 87 25 62 18 7 26 36 10 8 4 3 8 18 18 18 5 5 8 0 0 4 4 -1 -1 9 9 9 9 9 9 9
0 -1 -1 -1 0 -1 -1 9 5 0 0 -1 -1 9 9 9 5 5 8 0 0 4 4 -1 -1 9 9 9 9 9 9 9
0 9 8 9 8 4 9 9 5 8 4 4 9 9 9 9 5 5 8 0 0 4 4 -1 -1 9 9 9 9 9 9 9 

0 -3 -17 14 0 -17 2 12 4 -4 -8 -9 -4 6 6 6 5 -1 2 -6 -6 -2 -2 -7 -7 3 3 3 3 3 3 3
0 -7 -7 -7 -6 -7 -7 3 -1 -6 -6 -7 -7 3 3 3 5 -1 2 -6 -6 -2 -2 -7 -7 3 3 3 3 3 3 3 
0 5 5 3 5 -2 3 3 5 2 -2 -2 3 3 3 3 5 -1 2 -6 -6 -2 -2 -7 -7 3 3 3 3 3 3 3

0 101 23 78 8 15 34 44 4 4 8 7 12 22 22 22 5 -1 2 2 2 6 6 1 1 11 11 11 11 11 11 11 
0 -1 -1 1 -1 1 1 11 -1 2 2 1 1 11 11 11 5 -1 2 2 2 6 6 1 1 11 11 11 11 11 11 11
0 11 6 11 5 6 11 11 5 2 6 6 11 11 11 11 5 -1 2 2 2 6 6 1 1 11 11 11 11 11 11 11 

0 121 27 94 8 19 42 52 4 4 8 11 16 26 26 26 5 -1 2 2 2 6 8 3 3 13 13 13 13 13 13 13
0 -1 -1 3 -1 2 3 13 -1 2 2 3 3 13 13 13 5 -1 2 2 2 6 8 3 3 13 13 13 13 13 13 13
0 13 8 13 5 8 13 13 5 2 6 8 13 13 13 13 5 -1 2 2 2 6 8 3 3 13 13 13 13 13 13 13

0 41 -13 54 -12 -1 22 32 -6 -6 -2 1 6 16 16 16 0 -6 -3 -3 -3 1 3 -2 -2 8 8 8 8 8 8 8 
0 -6 -6 -2 -6 -3 -2 8 -6 -3 -3 -2 -2 8 8 8 0 -6 -3 -3 -3 1 3 -2 -2 8 8 8 8 8 8 8
0 8 3 8 0 3 8 8 0 -3 1 3 8 8 8 8 0 -6 -3 -3 -3 1 3 -2 -2 8 8 8 8 8 8 8
*/

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