Submission #587947

#	Time	Username	Problem	Language	Result	Execution time	Memory
587947		Clan328	Distributing Candies (IOI21_candies)	C++17	8 / 100	198 ms	17688 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;

struct segmentTree {
    vl t;

    segmentTree(int n) {
        t = vl(4*n);
    }

    void update(int v, int tl, int tr, int l, int r, ll add) {
        if (l > r)
            return;
        if (l == tl && r == tr) {
            t[v] += add;
        } else {
            int tm = (tl + tr) / 2;
            update(v*2, tl, tm, l, min(r, tm), add);
            update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
        }
    }

    ll get(int v, int tl, int tr, int pos) {
        if (tl == tr)
            return t[v];
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            return t[v] + get(v*2, tl, tm, pos);
        else
            return t[v] + get(v*2+1, tm+1, tr, pos);
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);

    segmentTree tree(n);

    for (int i = 0; i < l.size(); i++) {
        tree.update(1, 0, n-1, l[i], r[i], v[i]);
    }

    for (int i = 0; i < n; i++) {
        s[i] = min((ll)c[i], tree.get(1, 0, n-1, i));
    }

    return s;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~

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