oj.uz

Submission #566845

# Submission time Handle Problem Language Result Execution time Memory
566845 2022-05-23T03:39:36 Z PurpleCrayon Distributing Candies (IOI21_candies) C++17
0 / 100
 450 ms 54448 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 450 ms 54448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -