Submission #557859

#	Time	Username	Problem	Language	Result	Execution time	Memory
557859		TheWilp	Distributing Candies (IOI21_candies)	C++17	0 / 100	2567 ms	53736 KiB

candies

#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
using ll = long long;
ll maxll = (1ll << 62);
ll minll = -maxll;
ll lseg = 0;
ll rseg;
class name {
public:
    ll value = 0;
    ll pos = -1;
};
class segtree {
public:
    name max_value;
    name min_value;
    ll total_pus_max = 0;
    ll total_pus_min = 0;
    segtree* left = nullptr;
    segtree* right = nullptr;
};
void add_max(segtree* seg, ll left, ll right, ll s, ll e, ll number, ll total_pus = 0) {
    if (s <= left && right <= e) {
        seg->max_value.value += (number + total_pus);
        seg->total_pus_max += (number + total_pus);
        if (seg->max_value.pos == -1)
            seg->max_value.pos = left;
        return;
    }
    if (left > e || right < s) {
        seg->max_value.value += total_pus;
        seg->total_pus_max += total_pus;
        if (seg->max_value.pos == -1)
            seg->max_value.pos = left;
        return;
    }
    int mid = (left + right) / 2;
    total_pus += seg->total_pus_max;
    seg->total_pus_max = 0;
    if (seg->left == nullptr)
        seg->left = new segtree;
    if (seg->right == nullptr)
        seg->right = new segtree;
    add_max(seg->left, left, mid, s, e, number, total_pus);
    add_max(seg->right, mid + 1, right, s, e, number, total_pus);
    if (seg->left->max_value.value >= seg->right->max_value.value) {
        seg->max_value.value = seg->left->max_value.value;
        seg->max_value.pos = seg->left->max_value.pos;
    }
    else {
        seg->max_value.value = seg->right->max_value.value;
        seg->max_value.pos = seg->right->max_value.pos;
    }
}
void add_min(segtree* seg, ll left, ll right, ll s, ll e, ll number, ll total_pus = 0) {
    if (s <= left && right <= e) {
        seg->min_value.value += (number + total_pus);
        seg->total_pus_min += (number + total_pus);
        if (seg->min_value.pos == -1)
            seg->min_value.pos = left;
        return;
    }
    if (left > e || right < s) {
        seg->min_value.value += total_pus;
        seg->total_pus_min += total_pus;
        if (seg->min_value.pos == -1)
            seg->min_value.pos = left;
        return;
    }
    int mid = (left + right) / 2;
    total_pus += seg->total_pus_min;
    seg->total_pus_min = 0;
    if (seg->left == nullptr)
        seg->left = new segtree;
    if (seg->right == nullptr)
        seg->right = new segtree;
    add_min(seg->left, left, mid, s, e, number, total_pus);
    add_min(seg->right, mid + 1, right, s, e, number, total_pus);
    if (seg->left->min_value.value <= seg->right->min_value.value) {
        seg->min_value.value = seg->left->min_value.value;
        seg->min_value.pos = seg->left->min_value.pos;
    }
    else {
        seg->min_value.value = seg->right->min_value.value;
        seg->min_value.pos = seg->right->min_value.pos;
    }
}
name get_max(segtree* seg, ll left, ll right, ll s, ll e) {
    if (seg == nullptr)
        return { 0,left };
    if (s <= left && right <= e)
        return { seg->max_value.value,seg->max_value.pos };
    if (left > e || right < s)
        return { minll,left };
    int mid = (right + left) / 2;
    name get1 = get_max(seg->left, left, mid, s, e);
    name get2 = get_max(seg->right, mid + 1, right, s, e);
    if (get1.value >= get2.value) {
        get1.value += seg->total_pus_max;
        return get1;
    }
    else {
        get2.value += seg->total_pus_max;
        return get2;
    }
}
name get_min(segtree* seg, ll left, ll right, ll s, ll e) {
    if (seg == nullptr)
        return { 0,left };
    if (s <= left && right <= e)
        return { seg->min_value.value,seg->min_value.pos };
    if (left > e || right < s)
        return { maxll,left };
    int mid = (right + left) / 2;
    name get1 = get_min(seg->left, left, mid, s, e);
    name get2 = get_min(seg->right, mid + 1, right, s, e);
    if (get1.value <= get2.value) {
        get1.value += seg->total_pus_min;
        return get1;
    }
    else {
        get2.value += seg->total_pus_min;
        return get2;
    }
}
class Query {
public:
    ll t;
    ll pos;
    ll c;
    bool operator<(const Query b) const {
        return pos < b.pos;
    }
}put_in;
std::vector<Query> Q;
std::vector<int> result;
segtree* seg = new segtree;
name bsearch_max(int c) {
    int L = -1;
    int R = rseg - 1;
    while (R - L > 1) {
        int mid = (R + L) / 2;
        name get1 = get_max(seg, lseg, rseg, mid, rseg);
        name get2 = get_min(seg, lseg, rseg, get1.pos, rseg);
        if (get1.value - get2.value <= c) {
            R = mid;
        }
        else
            L = mid;
    }
    return get_max(seg,lseg,rseg,R,rseg);
}
name bsearch_min(int c) {
    int L = -1;
    int R = rseg - 1;
    while (R - L > 1) {
        int mid = (R + L) / 2;
        name get1 = get_min(seg, lseg, rseg, mid, rseg);
        name get2 = get_max(seg, lseg, rseg, get1.pos, rseg);
        if (get2.value - get1.value <= c) {
            R = mid;
        }
        else
            L = mid;
    }
    return get_min(seg, lseg, rseg, R, rseg);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    add_max(seg, lseg, rseg, 0, 0, 0);
    add_min(seg, lseg, rseg, 0, 0, 0);
    rseg = v.size() + 1;
    for (int q = 0; q < l.size(); q++) {
        put_in.t = q + 1;
        put_in.c = v[q];
        put_in.pos = l[q];
        Q.push_back(put_in);
        put_in.t = q + 1;
        put_in.c = -v[q];
        put_in.pos = r[q] + 1;
        Q.push_back(put_in);
    }
    std::sort(Q.begin(), Q.end());
    int i = 0;
    for (int q = 0; q < c.size(); q++) {
        if (i < Q.size()) {
            while (Q[i].pos == q) {
                add_max(seg, lseg, rseg, Q[i].t, rseg, Q[i].c);
                add_min(seg, lseg, rseg, Q[i].t, rseg, Q[i].c);
                ++i;
                if (i >= Q.size())
                    break;
            }
        }
        name get1 = bsearch_max(c[q]);
        name get2 = bsearch_min(c[q]);
        if (get1.pos < get2.pos) {
            result.push_back(c[q] + get_max(seg, lseg, rseg, rseg, rseg).value - get1.value);
        }
        else if (get1.pos == get2.pos) {
            if (get1.value >= c[q])
                result.push_back(c[q]);
            else
                result.push_back(0);
        }
        else {
            result.push_back(get_max(seg, lseg, rseg, rseg, rseg).value - get2.value);
        }
    }
    return result;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:175:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for (int q = 0; q < l.size(); q++) {
      |                     ~~^~~~~~~~~~
candies.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for (int q = 0; q < c.size(); q++) {
      |                     ~~^~~~~~~~~~
candies.cpp:188:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |         if (i < Q.size()) {
      |             ~~^~~~~~~~~~
candies.cpp:193:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |                 if (i >= Q.size())
      |                     ~~^~~~~~~~~~~

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