oj.uz

Submission #22294

# Submission time Handle Problem Language Result Execution time Memory
22294 2017-04-30T03:41:01 Z 카시코이(#958, xdoju, ntopia, pps789) Young Zebra (KRIII5_YZ) C++
Compilation error
 0 ms 0 KB 
#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

YZ.cpp: In function 'int main()':
YZ.cpp:77:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  segs.push_back(Seg{ -1, 0, 0, 0ll });
                    ^
YZ.cpp:83:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
   ramp[i] = Ramp{ x, d, t, p };
                 ^
YZ.cpp:94:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
   segs.push_back(Seg{ st, ed, i + 1, time });
                     ^
YZ.cpp:99:2: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
  });
  ^
YZ.cpp:99:3: error: no matching function for call to 'sort(std::vector<Seg>::iterator, std::vector<Seg>::iterator, main()::<lambda(const Seg&, const Seg&)>)'
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from YZ.cpp:4:
/usr/include/c++/5/bits/stl_algo.h:4689:5: note: candidate: template<class _RAIter> void std::sort(_RAIter, _RAIter)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     ^
/usr/include/c++/5/bits/stl_algo.h:4689:5: note:   template argument deduction/substitution failed:
YZ.cpp:99:3: note:   candidate expects 2 arguments, 3 provided
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from YZ.cpp:4:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note: candidate: template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   template argument deduction/substitution failed:
YZ.cpp: In substitution of 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<Seg*, std::vector<Seg> >; _Compare = main()::<lambda(const Seg&, const Seg&)>]':
YZ.cpp:99:3:   required from here
YZ.cpp:99:3: error: template argument for 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)' uses local type 'main()::<lambda(const Seg&, const Seg&)>'
  });
   ^
YZ.cpp:99:3: error:   trying to instantiate 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
YZ.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < segs.size(); ++i) {
                    ^
YZ.cpp:115:3: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
   auto bt1res = bt1.query(istidx, (int)eds.size() - 1);
   ^
YZ.cpp:115:8: error: 'bt1res' does not name a type
   auto bt1res = bt1.query(istidx, (int)eds.size() - 1);
        ^
YZ.cpp:116:20: error: 'bt1res' was not declared in this scope
   long long vala = bt1res.first - segs[i].st + segs[i].time;
                    ^
YZ.cpp:122:3: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
   auto bt2res = bt2.query(1, istidx - 1);
   ^
YZ.cpp:122:8: error: 'bt2res' does not name a type
   auto bt2res = bt2.query(1, istidx - 1);
        ^
YZ.cpp:123:20: error: 'bt2res' was not declared in this scope
   long long valb = bt2res.first + segs[i].st + segs[i].time;
                    ^
YZ.cpp:113:7: warning: unused variable 'istidx' [-Wunused-variable]
   int istidx = lower_bound(eds.begin(), eds.end(), segs[i].st) - eds.begin();
       ^
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:157:15: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for (int v : vector<int>(trace.rbegin(), trace.rend())) {
               ^
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);
                                       ^