Submission #1195211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195211		madamadam3	Distributing Candies (IOI21_candies)	C++20	8 / 100	69 ms	9032 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 << " "

typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;

struct Fenw {
    int n;
    vl bit;

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

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

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

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

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

        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], v[j]);
    }

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

    return s;
}

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