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;
}