Submission #1195209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195209		madamadam3	Distributing Candies (IOI21_candies)	C++20	0 / 100	62 ms	8332 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define each(a, x) for (auto &x : a) 
#define srt(x) sort(all(x))
#define sz(x) (int) (x).size()
#define pb push_back
#define trace(x) for (auto &el : x) cout << el << " "

using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;

struct Fenw {
    int n;
    vi bit;

    Fenw(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    int g(int i) {
        return i & (i + 1);
    }

    int h(int i) {
        return i | (i + 1);
    }

    void update_point(int r, int delta) {
        while (r < n) {
            bit[r] += delta;
            r = h(r);
        }
    }
    
    void update_range(int l, int r, int delta) {
        update_point(l, delta);
        update_point(r + 1, -delta);
    }

    int query(int idx) {
        int res = 0;
        while (idx >= 0) {
            res += bit[idx];
            idx = g(idx);
        }

        return res;
    }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = sz(c);
    int q = sz(r);
    vi s(n);

    // FOR(j, 0, q) {
    //     FOR(i, l[j], r[j] + 1) {
    //         s[i] = v[j] > 0 ? min(c[i], s[i] + v[j]) : max(0, s[i] + v[j]);
    //     }
    // }

    vi difference(n + 1, 0);
    FOR(j, 0, q) {
        difference[l[j]] += v[j];
        difference[r[j] + 1] -= v[j]; 
    }

    FOR(i, 1, n + 1) {
        difference[i] += difference[i - 1];
    }

    // trace(difference); cout << "\n";
    
    FOR(i, 0, n) {
        s[i] = min(c[i], difference[i]);
    }

    // auto fenw = Fenw(n);
    // FOR(j, 0, q) {
    //     fenw.update_range(l[j], r[j]+1, v[j]);
    // }

    // FOR(i, 0, n) {
    //     s[i] = min(c[i], fenw.query(i));
    // }

    return s;
}

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