Submission #1241541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241541		someone	Distributing Candies (IOI21_candies)	C++17	100 / 100	389 ms	39496 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Node {
    int mini = 0, maxi = 0, tag = 0;
};

vector<Node> node;
const int INF = 1e15;

void applyOp(int i, int add) {
    node[i].tag += add;
    node[i].mini += add;
    node[i].maxi += add;
}

void propage(int i) {
    applyOp(i*2, node[i].tag);
    applyOp(i*2+1, node[i].tag);
    node[i].tag = 0;
}

pair<int, int> query(int i, int deb, int fin, int l, int r, int add) {
    if(l <= deb && fin <= r) {
        applyOp(i, add);
        return {node[i].mini, node[i].maxi};
    }
    if(r <= deb || fin <= l) return {INF, -INF};
    propage(i);
    int mid = (deb + fin) >> 1;
    auto ansL = query(i*2, deb, mid, l, r, add),
         ansR = query(i*2+1, mid, fin, l, r, add);
    ansL.first = min(ansL.first, ansR.first);
    ansL.second = max(ansL.second, ansR.second);
    node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
    node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
    return ansL;
}

int getPos(int i, int deb, int fin, int mini, int maxi, int cap) {
    if(fin - deb == 1) return deb;
    int mid = (deb + fin) >> 1;
    propage(i);

    int midMin = min(mini, node[i*2+1].mini),
        midMax = max(maxi, node[i*2+1].maxi);
    int ans = 0;
    if(midMax - midMin >= cap) ans = getPos(i*2+1, mid, fin, mini, maxi, cap);
    else ans = getPos(i*2, deb, mid, midMin, midMax, cap);
    node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
    node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
    return ans;
}

vector<int> a;/*
pair<int, int> query(int j, int deb, int fin, int l, int r, int add) {
    for(int i = l; i < r; i++)
        a[i] += add;
    int mini = a[l], maxi = a[l];
    for(int i = l; i < r; i++) {
        mini = min(mini, a[i]);
        maxi = max(maxi, a[i]);
    }
    return {mini, maxi};
}

int getPos(int i, int deb, int fin, int mini, int maxi, int cap) {
    int id = fin;
    while(id > 0 && maxi - mini < cap) {
        id--;
        maxi = max(maxi, a[id]);
        mini = min(mini, a[id]);
    }
    return id;
}*/

vector<signed> distribute_candies(vector<signed> c, vector<signed> l,
                               vector<signed> r, vector<signed> v) {
    int n = c.size(), q = l.size();
    node.resize(4*(q+1));
    a.resize(q+1);

    vector<vector<int>> req(n+1);
    for(int i = 0; i < q; i++) {
        req[l[i]].push_back(i);
        req[r[i]+1].push_back(i);
    }
    vector<signed> ans(n);
    for(int i = 0; i < n; i++) {
        for(int id : req[i]) {
            int val = v[id];
            if(i == r[id]+1)
                val = -v[id];
            query(1, 0, q+1, id+1, q+1, val);
        }
        int pos = getPos(1, 0, q+1, INF, -INF, c[i]);
        auto [mini, maxi] = query(1, 0, q+1, pos, q+1, 0);
        auto [valPos, _0] = query(1, 0, q+1, pos, pos+1, 0);
        auto [valFin, _1] = query(1, 0, q+1, q, q+1, 0);

        if(pos == 0 && maxi - mini < c[i]) {
            ans[i] = (signed)(valFin - mini);
        } else if(mini == valPos) {
            ans[i] = (signed)(valFin - maxi + c[i]);
        } else {
            ans[i] = (signed)(valFin - mini);
        }
    }
    return ans;
}

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