NKTARDY - Lập lịch giảm thiểu trễ hạn

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

const int N = 100005;
const int INF = N;

using namespace std;

struct job {
    int index;
    int time, limit;
} a[N];
int n;

bool incTime(const job &a, const job &b) { return a.time < b.time; }
bool incLimit(const job &a, const job &b) { return a.limit < b.limit; }

struct node {
    int l, r;
    int minV, lazy;
    node *left, *right;

    node(int _l, int _r) {
        l = _l; r = _r;
        minV = INF; lazy = 0;
        left = right = NULL;
    }

    void pushDown() {
        if (l < r && left == NULL) {
            left = new node(l, l + r >> 1);
            right = new node((l + r >> 1) + 1, r);
        }
        if (lazy) {
            minV -= lazy;
            if (l < r) {
                left->lazy += lazy;
                right->lazy += lazy;
            }
            lazy = 0;
        }
    }

    void assign(int i, int v) {
        pushDown();
        if (r < i || i < l) return;
        if (l == r) {
            minV = v;
            return;
        }
        left->assign(i, v);
        right->assign(i, v);
        minV = min(left->minV, right->minV);
    }

    void decSuffix(int from, int value) {
        pushDown();
        if (r < from) return;
        if (from <= l) {
            lazy += value;
            pushDown();
            return;
        }
        left->decSuffix(from, value);
        right->decSuffix(from, value);
        minV = min(left->minV, right->minV);
    }

    int suffixMin(int from) {
        pushDown();
        if (r < from) return INF;
        if (from <= l) return minV;
        return min(left->suffixMin(from), right->suffixMin(from));
    }
};

struct T_BIT {
    int bit[N];

    T_BIT() {
        memset(bit, 0, sizeof(bit));
    }

    void update(int i, int v) {
        for (++i; i < N; i += i & -i)
            bit[i] += v;
    }

    int prefixSum(int i) {
        int ans = 0;
        for (++i; i > 0; i -= i & -i)
            ans += bit[i];
        return ans;
    }
} BIT;

int order[N];
bool was[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
    freopen("NKTARDY.txt", "r", stdin);
#endif // _LAD_
    cin >> n;
    for (int i = 0; i < n; ++i) a[i].index = i;
    for (int i = 0; i < n; ++i) cin >> a[i].time;
    for (int i = 0; i < n; ++i) cin >> a[i].limit;
    node *root = new node(0, n - 1);
    sort(a, a + n, incLimit);
    for (int i = 0; i < n; ++i) order[a[i].index] = i;
    sort(a, a + n, incTime);
    vector<job> ans;
    for (int i = 0; i < n; ++i) {
        int pos = order[a[i].index];
        int minFree = root->suffixMin(pos);
        int curTime = BIT.prefixSum(pos);
        if (curTime + a[i].time <= a[i].limit && a[i].time <= minFree) {
            ans.push_back(a[i]);
            root->decSuffix(pos, a[i].time);
            root->assign(pos, a[i].limit - curTime - a[i].time);
            BIT.update(pos, a[i].time);
        }
    }
    cout << n - ans.size() << endl;
    for (job it: ans) was[it.index] = 1;
    sort(ans.begin(), ans.end(), incLimit);
    for (int i = 0; i < n; ++i) if (!was[a[i].index]) ans.push_back(a[i]);
    for (job it: ans) cout << it.index + 1 << ' ';
    return 0;
}

Download