Submission #1084575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084575		Swan	Distributing Candies (IOI21_candies)	C++17	0 / 100	210 ms	29380 KiB

candies

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
//#define int long long
#define INP freopen("palpath.in","r",stdin)
#define OUTP freopen("palpath.out","w",stdout)
using ld = long double;
using LD = ld;
 
using namespace std;

const int maxn = 5 * 2e5;

struct node {
    long long add;
    long long minus;

    node() {
        this->add = 0;
        this->minus = 0;
    }
};

node tree[maxn];

void propogate(int v, int l, int r) {
    if (l == r) return;

    if (tree[v].add >= 0) { 
        tree[v * 2].minus -= min(tree[v].add, tree[v * 2].minus);
        tree[v * 2].add += tree[v].add - min(tree[v].add, tree[v * 2].minus);

        tree[v * 2 + 1].minus -= min(tree[v].add, tree[v * 2 + 1].minus);
        tree[v * 2 + 1].add += tree[v].add - min(tree[v].add, tree[v * 2 + 1].minus);
    
        tree[v].add = 0;
    }

    if (tree[v].minus >= 0) { 
        tree[v * 2].minus += tree[v].minus;
        tree[v * 2 + 1].minus += tree[v].minus;

        tree[v].minus = 0;
    }
}

void applyOp(int v, int val) {
    if (val < 0)tree[v].minus+=abs(val);
    if (val > 0)tree[v].add+=val;
}

void update(int v, int l, int r, int le, int re, long long val) {
    propogate(v, l, r);
    if (l > re || r < le) return;
    if (l >= le && r <= re) {
        applyOp(v, val);
        return;
    }

    int m = (l + r) / 2;

    update(v * 2, l, m, le, re, val);
    update(v * 2 + 1, m + 1, r, le, re, val);
}

long long getVal(int v, int l, int r, int need, long long c) {
    propogate(v, l, r);
    if (l == r) {
       // cout << "WOW " << tree[v].add << ' ' << tree[v].minus << endl;
        return max(0ll, min(tree[v].add, c) - tree[v].minus);
    }

    int m = (l + r) / 2;
    if (need <= m) return getVal(v * 2, l, m, need, c);
    else return getVal(v * 2 + 1, m + 1, r, need, c);
}

vector<long long> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    for (int i = 0; i < l.size(); i++) {
        int curL = l[i];
        int curR = r[i];
        long long val = v[i];

        update(1, 0, c.size() - 1, curL, curR, val);
        //break;
    }

    vector<long long> ans;

    for (int i = 0; i < c.size(); i++) {
        ans.push_back(getVal(1, 0, c.size() - 1, i, c[i]));
    }

    return ans;
}
/*
int main(){
    ios_base::sync_with_stdio(0);
    vector<long long> ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
    for (auto a : ans) cout << a << ' ';
    return 0;
}   */

Compilation message (stderr)

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

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