Submission #1309919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309919		michael12	Distributing Candies (IOI21_candies)	C++20	0 / 100	156 ms	13724 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200005;
struct segtree {
    vector<int> tree, lazy;
    int     n;
    segtree(int n) : n(n) {
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }
    // void build(int node, int start, int end, const vector<int> &a) {
    //     if (start == end) {
    //         tree[node] = a[start];
    //         return;
    //     }
    //     int mid = (start + end) / 2;
    //     build(2 * node, start, mid, a);
    //     build(2 * node + 1, mid + 1, end, a);
    //     tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    // }
    void push(int node, int start, int end, const vector<int>& c) {
    if(lazy[node] != 0) {
        if(start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        } else {
            tree[node] += lazy[node];
            tree[node] = max(0, min(tree[node], c[start])); 
        }
        lazy[node] = 0;
    }
}


    void update(int node, int start, int end, int l, int r, int val, vector<int>& c) {
        push(node, start, end, c);
        if (start > r || end < l) return;
        if (l <= start && end <= r) {
            lazy[node] += val;
            push(node, start, end, c);
            return;
        }
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, val, c);
        update(2 * node + 1, mid + 1, end, l, r, val, c);
    }
    int get(int node, int start, int end, int id, vector<int>& c){
        push(node, start, end, c);
        if(start == end){
           return tree[node];
        }
        else{
            int mid = (start + end) / 2;
            if(mid >= id){
                return get(2 * node, start, mid, id, c);
            }
            else{
                return get(2 * node + 1, mid + 1, end, id, c);
            }
        }
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
     int sz = c.size();
     segtree ST(sz);
     for(int dy = 0; dy < v.size(); dy++){
          ST.update(1, 0, sz - 1, l[dy], r[dy], v[dy], c);
     }
     vector<int> ans(sz);
     for(int i = 0; i < sz; i++){
         ans[i] = ST.get(1, 0, sz - 1, i, c);
     }
     return ans;
}

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