| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22294 | 카시코이 (#40) | Young Zebra (KRIII5_YZ) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const long long INFLL = 100000000000000000ll;
int n, L;
struct Ramp {
int x, d, t, p;
};
Ramp ramp[100001];
struct Seg {
long long st, ed;
int id;
long long time;
};
vector<Seg> segs;
long long d[100001];
int tr[100001];
const int TSIZE = 131072;
struct BTree {
vector<long long> tree;
vector<int> idx;
BTree() : tree(TSIZE * 2 + 1, INFLL), idx(TSIZE * 2 + 1, -1) {
}
void update(int pos, long long val, int id) {
pos |= TSIZE;
if (tree[pos] > val) {
tree[pos] = val;
idx[pos] = id;
}
while (pos >>= 1) {
if (tree[pos << 1] < tree[pos << 1 | 1]) {
tree[pos] = tree[pos << 1];
idx[pos] = idx[pos << 1];
}
else {
tree[pos] = tree[pos << 1 | 1];
idx[pos] = idx[pos << 1 | 1];
}
}
}
pair<long long, int> query(int l, int r) {
l |= TSIZE;
r |= TSIZE;
long long ret = INFLL;
int retidx = -1;
while (l <= r) {
if (l & 1) {
if (ret > tree[l]) {
ret = tree[l];
retidx = idx[l];
}
}
if ((r & 1) == 0) {
if (ret > tree[r]) {
ret = tree[r];
retidx = idx[r];
}
}
l = (l + 1) >> 1;
r = (r - 1) >> 1;
}
return make_pair(ret, retidx);
}
};
BTree bt1, bt2;
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &L);
segs.push_back(Seg{ -1, 0, 0, 0ll });
vector<long long> eds;
eds.push_back(-10000000003ll);
for (int i = 0; i < n; ++i) {
int x, d, t, p;
scanf("%d %d %d %d", &x, &d, &t, &p);
ramp[i] = Ramp{ x, d, t, p };
long long st = (long long)x - p;
long long ed = (long long)x + d;
long long time = (long long)p + t;
if (ed - st <= time) {
continue;
}
if (st < 0 || ed > L) {
continue;
}
segs.push_back(Seg{ st, ed, i + 1, time });
eds.push_back(ed);
}
sort(segs.begin(), segs.end(), [](const Seg& a, const Seg& b) {
return a.st < b.st;
});
sort(eds.begin(), eds.end());
eds.erase(unique(eds.begin(), eds.end()), eds.end());
eds.push_back(10000000003ll);
long long ans = L;
int ansidx = -1;
d[0] = 0;
tr[0] = -1;
for (int i = 1; i < segs.size(); ++i) {
d[i] = segs[i].st + segs[i].time;
tr[i] = -1;
int istidx = lower_bound(eds.begin(), eds.end(), segs[i].st) - eds.begin();
auto bt1res = bt1.query(istidx, (int)eds.size() - 1);
long long vala = bt1res.first - segs[i].st + segs[i].time;
if (bt1res.first < INFLL && d[i] > vala) {
d[i] = vala;
tr[i] = bt1res.second;
}
auto bt2res = bt2.query(1, istidx - 1);
long long valb = bt2res.first + segs[i].st + segs[i].time;
if (bt2res.first < INFLL && d[i] > valb) {
d[i] = valb;
tr[i] = bt2res.second;
}
/*
for (int j = i - 1; j > 0; --j) {
if (segs[i].st == segs[j].st) {
continue;
}
d[i] = min(d[i], d[j] + llabs((long long)segs[j].ed - segs[i].st) + segs[i].time);
}
*/
long long valt = d[i] + (L - segs[i].ed);
if (ans > valt) {
ans = valt;
ansidx = i;
}
int iedidx = lower_bound(eds.begin(), eds.end(), segs[i].ed) - eds.begin();
bt1.update(iedidx, d[i] + segs[i].ed, i);
bt2.update(iedidx, d[i] - segs[i].ed, i);
}
printf("%lld\n", ans);
vector<int> trace;
while (ansidx != -1) {
trace.push_back(ansidx);
ansidx = tr[ansidx];
}
printf("%d\n", trace.size());
for (int v : vector<int>(trace.rbegin(), trace.rend())) {
printf("%d ", segs[v].id);
}
putchar('\n');
return 0;
}