Submission #566845

#	Time	Username	Problem	Language	Result	Execution time	Memory
566845		PurpleCrayon	사탕 분배 (IOI21_candies)	C++17	0 / 100	450 ms	54448 KiB

candies

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

#define ar array
#define sz(v) int(v.size())
typedef long long ll;

struct Line {
    ll x, y;
};

struct LineBeats {
    vector<Line> mins, maxes;
    ll start = 0;

    LineBeats() {}

    void add_min(Line me) {
        bool add = 0;
        for (Line l : mins) {
            if (l.x == me.x) {
                l.y = min(l.y, me.y);
                add = 1;
            } 
        }
        if (!add) mins.push_back(me);
    }
    void add_max(Line me) {
        bool add = 0;
        for (Line l : maxes) {
            if (l.x == me.x) {
                l.y = max(l.y, me.y);
                add = 1;
            } 
        }
        if (!add) maxes.push_back(me);
    }
    void add_scalar(int x) {
        start += x;
        for (auto& l : mins) l.y += x;
        for (auto& l : maxes) l.y += x;
    }
    int qry(int x) {
        ll ans = start;
        for (auto& l : mins) ans = min(ans, l.x * x + l.y);
        for (auto& l : maxes) ans = max(ans, l.x * x + l.y);
        return ans;
    }
};

vector<vector<int>> tree;
vector<int> ans, c;

void upd(int v, int tl, int tr, int l, int r, int x) {
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        tree[v].push_back(x);
        return;
    }
    int tm = (tl + tr) / 2;
    upd(2*v, tl, tm, l, r, x), upd(2*v+1, tm+1, tr, l, r, x);
}
void rec(int v, int tl, int tr, LineBeats lines) {
    for (int x : tree[v]) {
        lines.add_scalar(x);
        if (x < 0) {
            lines.add_max({0, 0}); // max with 0
        } else {
            lines.add_min({1, 0}); // min with c
        }
    }
    if (tl == tr) {
        ans[tl] = lines.qry(c[tl]);
    } else {
        int tm = (tl + tr) / 2;
        rec(2*v, tl, tm, lines), rec(2*v+1, tm+1, tr, lines);
    }
}
vector<int> distribute_candies(vector<int> _c, vector<int> l, vector<int> r, vector<int> v) {
    int n = _c.size(), q = l.size();

    tree.resize(4 * n);
    ans.resize(n);
    c = _c;

    for (int qt = 0; qt < q; qt++) {
        int L = l[qt], R = r[qt], x = v[qt];
        upd(1, 0, n-1, L, R, x);
    }
    rec(1, 0, n-1, LineBeats());
    return ans;
}

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