Submission #22351

#TimeUsernameProblemLanguageResultExecution timeMemory
22351카시코이 (#40)Young Zebra (KRIII5_YZ)C++14
0 / 7
0 ms10832 KiB
#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; }

Compilation message (stderr)

YZ.cpp: In function 'int main()':
YZ.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < segs.size(); ++i) {
                    ^
YZ.cpp:156:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", trace.size());
                             ^
YZ.cpp:76:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &L);
                        ^
YZ.cpp:82:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x, &d, &t, &p);
                                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...