Submission #451959

#	Time	Username	Problem	Language	Result	Execution time	Memory
451959		vector	Distributing Candies (IOI21_candies)	C++17	100 / 100	2960 ms	36292 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define SIZE 200001
using namespace std;
typedef long long ll;
ll lazy[4*SIZE], max_tree[4*SIZE], min_tree[4*SIZE];
vector<pair<int, int> > query[SIZE];
void pro(int node)
{
    lazy[node*2]+=lazy[node];
    lazy[node*2+1]+=lazy[node];
    max_tree[node*2]+=lazy[node];
    max_tree[node*2+1]+=lazy[node];
    min_tree[node*2]+=lazy[node];
    min_tree[node*2+1]+=lazy[node];
    lazy[node]=0;
}
void upd(int s, int e, int w, int l, int r, int node)
{
    if (l>r) return;
    if (s<=l && r<=e) {
        lazy[node]+=w;
        max_tree[node]+=w;
        min_tree[node]+=w;
        return;
    }
    if (l>e || s>r) return;
    pro(node);
    int mid=(l+r)/2;
    upd(s, e, w, l, mid, node*2);
    upd(s, e, w, mid+1, r, node*2+1);
    max_tree[node]=max(max_tree[node*2], max_tree[node*2+1]);
    min_tree[node]=min(min_tree[node*2], min_tree[node*2+1]);
}
ll get_max(int s, int e, int l, int r, int node)
{
    if (l>r) return -1e18;
    if (s<=l && r<=e) return max_tree[node];
    if (l>e || s>r) return -1e18;
    int mid=(l+r)/2;
    pro(node);
    return max(get_max(s, e, l, mid, node*2), get_max(s, e, mid+1, r, node*2+1));
}
ll get_min(int s, int e, int l, int r, int node)
{
    if (l>r) return 1e18;
    if (s<=l && r<=e) return min_tree[node];
    if (l>e || s>r) return 1e18;
    int mid=(l+r)/2;
    pro(node);
    return min(get_min(s, e, l, mid, node*2), get_min(s, e, mid+1, r, node*2+1));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int N=c.size(), M=l.size();
    vector<int> ans(N);
    for (int i=0; i<M; i++) {
        query[l[i]].push_back(make_pair(v[i], i));
        query[r[i]+1].push_back(make_pair(-v[i], i));
    }
    for (int i=0; i<N; i++) {
        for (auto j : query[i]) upd(j.second+1, M, j.first, 0, M, 1);
        if (get_max(0, M, 0, M, 1)-get_min(0, M, 0, M, 1)<=c[i]) ans[i]=get_max(M, M, 0, M, 1)-get_min(0, M, 0, M, 1);
        else {
            int s=0, e=M, mid;
            while (1) {
                if (s>=e) break;
                mid=(s+e)/2;
                if (get_max(mid, M, 0, M, 1)-get_min(mid, M, 0, M, 1)<=c[i]) e=mid;
                else s=mid+1;
            }
            if (get_max(s-1, s-1, 0, M, 1)<get_min(s, M, 0, M, 1)) ans[i]=c[i]-get_max(s, M, 0, M, 1)+get_max(M, M, 0, M, 1);
            else ans[i]=get_max(M, M, 0, M, 1)-get_min(s, M, 0, M, 1);
        }
    }
    return ans;
}

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