Submission #22332

#	Time	Username	Problem	Language	Result	Execution time	Memory
22332		카시코이 (#40)	Young Zebra (KRIII5_YZ)	C++14	0 / 7	3 ms	10832 KiB

YZ

#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);
                                       ^

• Subtask 1: 0 / 7