Submission #712160

#	Time	Username	Problem	Language	Result	Execution time	Memory
712160		danikoynov	Keys (IOI21_keys)	C++17	Compilation error	0 ms	0 KiB

keys

#include "candies.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

int n, q;
ll add[maxn], rem[maxn];
vector < int > s;
pair < int, int > cap[maxn];

struct lazy_node
{
    ll val, set_to_0, set_to_max;

    lazy_node()
    {
        val = set_to_0 = set_to_max = 0;
    };
};

ll tree[4 * maxn];
lazy_node lazy[4 * maxn];

void push_lazy(int root, int left, int right)
{
    if (left == right)
    {
        if (lazy[root].set_to_0)
            tree[root] = 0;
        if (lazy[root].set_to_max)
            tree[root] = cap[left].first;
        tree[root] += lazy[root].val;
        lazy[root] = lazy_node();
        return;
    }

    if (lazy[root].set_to_0 || lazy[root].set_to_max)
    {
        lazy[root * 2] = lazy[root];
        lazy[root * 2 + 1] = lazy[root];
    }
    else
    {
        lazy[root * 2].val += lazy[root].val;
        lazy[root * 2 + 1].val += lazy[root].val;
    }

    lazy[root] = lazy_node();
}

void update_range(int root, int left, int right, int qleft, int qright, lazy_node cur_lazy)
{
///cout << root << " " << left << " " << right << " " << endl;
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        //cout << tree[root] << endl;
        lazy[root] = cur_lazy;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright, cur_lazy);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, cur_lazy);
}

ll get_element(int root, int left, int right, int pos)
{
    push_lazy(root, left, right);
    if (left == right)
        return tree[root];

    int mid = (left + right) / 2;
    if (pos <= mid)
        return get_element(root * 2, left, mid, pos);
    else
        return get_element(root * 2 + 1, mid + 1, right, pos);
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v)
{
    n = c.size();
    q = l.size();
    s.resize(n, 0);
    bool all_positive = true, whole = true;
    for (int i = 0; i < q; i ++)
    {
        if (v[i] < 0)
            all_positive = false;
        if (l[i] != 0 || r[i] != n - 1)
            whole = false;
    }
    if (whole)
    {
        for (int i = 0; i < n; i ++)
            cap[i] = {c[i], i};

        sort(cap, cap + n);
        for (int i = 0; i < q; i ++)
        {
            if (v[i] > 0)
            {
                int lf = 0, rf = n - 1;
                while(lf <= rf)
                {
                    int mf = (lf + rf) / 2;
                    ll val = get_element(1, 0, n - 1, mf);
                    ///cout << lf << " : " << rf << " : " << val << " " << v[i] << " " << cap[mf].first << endl;
                    if (val + v[i] >= cap[mf].first)
                        lf = mf + 1;
                    else
                        rf = mf - 1;
                }


                if (rf != -1)
                {
                    lazy_node cur_lazy;
                    cur_lazy.set_to_max = 1;
                    update_range(1, 0, n - 1, 0, rf, cur_lazy);
                }
                if (rf != n - 1)
                {
                    lazy_node cur_lazy;
                    cur_lazy.val = v[i];
                    update_range(1, 0, n - 1, rf + 1, n - 1, cur_lazy);
                }

            }
            else
            {
                int lf = 0, rf = n - 1;
                while(lf <= rf)
                {
                    int mf = (lf + rf) / 2;
                    ll val = get_element(1, 0, n - 1, mf);
                    if (val + v[i] <= 0)
                        lf = mf + 1;
                    else
                        rf = mf - 1;
                }

                ///cout << rf << endl;

                if (rf != -1)
                {
                    lazy_node cur_lazy;
                    cur_lazy.set_to_0 = 1;
                    update_range(1, 0, n - 1, 0, rf, cur_lazy);
                }
                ///cout << "here" << endl;
                if (rf != n - 1)
                {
                    lazy_node cur_lazy;
                    cur_lazy.val = v[i];
                    update_range(1, 0, n - 1, rf + 1, n - 1, cur_lazy);
                }
                ///cout << "stop" << endl;
            }
        }

        for (int i = 0; i < n; i ++)
            s[cap[i].second] = get_element(1, 0, n - 1, i);
        return s;
    }
    if (all_positive)
    {
        for (int i = 0; i < q; i ++)
        {
            add[l[i]] += v[i];
            rem[r[i] + 1] += v[i];
        }

        ll sum = 0;
        for (int i = 0; i < n; i ++)
        {
            sum += add[i];
            sum -= rem[i];
            s[i] = min((ll)(c[i]), sum);
        }
        return s;
    }
    for (int i = 0; i < q; i ++)
    {
        for (int j = l[i]; j <= r[i]; j ++)
        {
            s[j] += v[i];
            if (s[j] < 0)
                s[j] = 0;
            if (s[j] > c[j])
                s[j] = c[j];
        }
    }
    return s;
}

Compilation message (stderr)

keys.cpp:1:10: fatal error: candies.h: No such file or directory
    1 | #include "candies.h"
      |          ^~~~~~~~~~~
compilation terminated.