Submission #837743

#	Time	Username	Problem	Language	Result	Execution time	Memory
837743		Kerim	Distributing Candies (IOI21_candies)	C++17	100 / 100	760 ms	44196 KiB

candies

#include "candies.h"
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int N = 2e5+5;
vector<int> add[N], rem[N];
int arr[N];
struct node{
    ll mx, mn, sum;
    node(){
        mx = mn = sum = 0;
    }
    node(int v){
        mx = max(0, v);
        mn = min(0, v);
        sum = v;
    }
}s[N<<2];
node merge(node x, node y){
    node z;
    z.sum = x.sum + y.sum;
    z.mn = min(y.mn, x.mn + y.sum);
    z.mx = max(y.mx, x.mx + y.sum);
    return z;
}
void upd(int p, int v, int nd, int x, int y){
    if (x == y){
        arr[p] = v;
        s[nd] = node(v);
        return;
    }
    int mid = (x+y) >> 1;
    if (p <= mid)
        upd(p, v, nd << 1, x, mid);
    else    
        upd(p, v, nd<<1|1, mid+1, y);
    s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}
node get(int l, int r, int nd, int x, int y){
    if (l > y or x > r)
        return node();
    if (l <= x and y <= r)
        return s[nd];
    int mid = (x+y) >> 1;
    return merge(get(l, r, nd<<1, x, mid), get(l, r, nd<<1|1, mid+1, y));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    vector<int> s(n);
    for (int i = 0; i < q; i++){
        add[l[i]].push_back(i);
        rem[r[i]].push_back(i);
    }
    for (int i = 0; i < n; i++){
        for (auto pos: add[i])
            upd(pos, v[pos], 1, 0, q-1);
        int st = -1, en = q-1;
        while (st < en){
            int mid = (st + en + 1) >> 1;
            node res = get(mid, q-1, 1, 0, q-1);
            if (res.mx - res.mn > c[i])
                st = mid;
            else
                en = mid-1;
        }
        node res = get(max(st, 0), q-1, 1, 0, q-1);
        if (st >= 0){
            if (arr[st] > 0)
                s[i] = c[i] + res.mn;
            else
                s[i] = res.mx;
        }
        else    
            s[i] = res.mx;
        for (auto pos: rem[i])
            upd(pos, 0, 1, 0, q-1);
    }
    return s;
}

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