Submission #826581

#	Time	Username	Problem	Language	Result	Execution time	Memory
826581		Liudas	Distributing Candies (IOI21_candies)	C++17	0 / 100	870 ms	32200 KiB

candies

#include <iostream>
#include "candies.h"
#include <cassert>
#include <cstdio>
#include <climits>
#include <vector>
using namespace std;
class segtree{
public:
    struct node{
        long long mini;
        long long maxi;
        long long sum;
    };
    vector<node> tree;
    int N;
    void init(int n){
        N = 1;
        while(N <= n){
            N*=2;
        }
        tree.assign(2 * N, {0, 0, 0});
    }
    void update(int head, int L, int R, int pos, int val){
        if(R - L == 1){
            tree[head] = {val, val, val}; 
            return;
        }
        int mid = (L + R) / 2;
        if(pos < mid){
            update(head * 2 + 1, L, mid, pos, val);
        }
        else{
            update(head * 2 + 2, mid, R, pos, val);
        }
        tree[head].sum = tree[head * 2 + 1].sum + tree[head * 2 + 2].sum;
        tree[head].mini = min(tree[head * 2 + 2].sum + tree[head * 2 + 1].mini, tree[head * 2 + 2].mini);
        tree[head].maxi = max(tree[head * 2 + 2].sum + tree[head * 2 + 1].maxi, tree[head * 2 + 2].maxi);
    }
    void update(int pos, int val){
        update(0, 0, N, pos, val);
    }
    long long getmin(int head, int L, int R, int l, int r){
        if(l <= L && R <= r){
            return tree[head].mini;
        }
        if(l >= R || r <= L){
            return LLONG_MAX;
        }
        int mid = (L + R) / 2;
        return min(getmin(head * 2 + 1, L, mid, l, r), getmin(head * 2 + 2, mid, R, l, r));
    }
    long long getmin(int l, int r){
        return getmin(0, 0, N, l, r);
    }
    long long getmax(int head, int L, int R, int l, int r){
        if(l <= L && R <= r){
            return tree[head].maxi;
        }
        if(l >= R || r <= L){
            return LLONG_MIN;
        }
        int mid = (L + R) / 2;
        return max(getmax(head * 2 + 1, L, mid, l, r), getmax(head * 2 + 2, mid, R, l, r));
    }
    long long getmax(int l, int r){
        return getmax(0, 0, N, l, r);
    }
    long long getsum(int head, int L, int R, int l, int r){
        if(l <= L && R <= r){
            return tree[head].sum;
        }
        if(l >= R || r <= L){
            return 0;
        }
        int mid = (L + R) / 2;
        return getsum(head * 2 + 1, L, mid, l, r) + getsum(head * 2 + 2, mid, R, l, r);
    }
    long long getsum(int l, int r){
        return getsum(0, 0, N, l, r);
    }
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> val){
    int N = c.size();
    int Q = l.size();
    vector<int> ans(N);
    segtree tree;
    tree.init(Q);
    vector<int> vals(Q);
    vector<vector<pair<int, int>>> op(N + 5);
    for(int i = 0; i < Q; i ++){
        op[l[i]].push_back({i, val[i]});
        op[r[i]+1].push_back({i, 0});
    }
    for(int i = 0; i < N; i ++){
        for(auto[ll, rr] : op[i]){
            tree.update(ll, rr);
            vals[ll] = rr;
        }
        int L = 0, R = Q;
        long long a = 0, b = 0;
        while(L + 1 < R){
            int mid = (L + R) / 2;
            a = max(a, tree.getmax(mid, Q));
            b = min(b, tree.getmin(mid, Q));
            if(a - b > c[i]){
                L = mid;
            }
            else{
                R = mid;
            }
        }
        if(a - b <= c[i]){
            ans[i] = a;
        }
        else if(vals[L] < 0){
            ans[i] = a;
        } 
        else{
            ans[i] = c[i] + b;
        }
    }
    return ans;
}

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