Submission #826674

#	Time	Username	Problem	Language	Result	Execution time	Memory
826674		Liudas	Distributing Candies (IOI21_candies)	C++17	0 / 100	1327 ms	31456 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 lazy;
    };
    vector<node> tree;
    int N;
    void init(int n){
        N = 1;
        while(N <= n){
            N*=2;
        }
        tree.assign(2 * N, {0, 0, 0});
    }
    void lazy_upd(int head){
        tree[head].mini += tree[head].lazy;
        tree[head].maxi += tree[head].lazy;
        if(head < N){
            tree[head * 2 + 1].lazy += tree[head].lazy;
            tree[head * 2 + 2].lazy += tree[head].lazy;
        }
        tree[head].lazy = 0;
    }
    void update(int head, int L, int R, int l, int r, int val){
        lazy_upd(head);
        if(l <= L && R <= r){
            tree[head].lazy = val;
            lazy_upd(head); 
            return;
        }
        if(R <= l || r <= L){
            return;
        }
        int mid = (L + R) / 2;
        update(head * 2 + 1, L, mid, l, r, val);
        update(head * 2 + 2, mid, R, l, r, val);
        tree[head].mini = min(tree[head * 2 + 1].mini, tree[head * 2 + 2].mini);
        tree[head].maxi = max(tree[head * 2 + 1].maxi, tree[head * 2 + 2].maxi);
    }
    void update(int l, int val){
        update(0, 0, N, l, N, val);
    }
    long long getmin(int head, int L, int R, int l, int r){
        lazy_upd(head);
        if(l <= L && R <= r){
            return tree[head].mini;
        }
        if(R <= l || 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){
        return getmin(0, 0, N, l, N);
    }
    long long getmax(int head, int L, int R, int l, int r){
        lazy_upd(head);
        if(l <= L && R <= r){
            return tree[head].maxi;
        }
        if(R <= l || 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){
        return getmax(0, 0, N, l, N);
    }
    long long getpoint(int head, int L, int R, int x){
        lazy_upd(head);
        if(R - L == 1){
            return tree[head].mini;
        }
        int mid = (L + R) / 2;
        if(x < mid){
            return getpoint(head * 2 + 1, L, mid, x);
        }
        else{
            return getpoint(head * 2 + 2, mid, R, x);
        }
    }
    long long getpoint(int x){
        return getpoint(0, 0, N, x);
    }
};
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 + 5);
    vector<vector<pair<int, int>>> op(N + 5);
    for(int i = 0; i < Q; i ++){
        op[l[i]].push_back({i + 2, val[i]});
        op[r[i]+1].push_back({i + 2, -val[i]});
    }
    for(int i = 0; i < N; i ++){
        for(auto[ll, rr] : op[i]){
            tree.update(ll, rr);
        }
        int l = 0, r = Q + 1;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            if(tree.getmax(mid)-tree.getmin(mid) > c[i]){
                l = mid;
            }
            else{
                r = mid;
            }
        }
        //cout << tree.getpoint(l) << " " <<  tree.getpoint(Q + 1) << " " << l << endl;
        long long a = tree.getpoint(l), b = tree.getpoint(Q + 1);
        if(a < b){
            int d = tree.getmax(l);
            ans[i] = c[i] - (d - b);
        }
        else{
            int d = tree.getmin(l);
            ans[i] = b - d;
        }
    }
    return ans;
}

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