Submission #673195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
673195	2022-12-19T22:12:16 Z	US3RN4M3	Event Hopping (BOI22_events)	C++17	Compilation error	0 ms	0 KB

events

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100005;
const int inf = 1e9;
int n, q;
pair<int, int> intervals[mx];
int ans[mx];
struct qd {
	set<pair<int, pair<int, int>>> qs;
	int cost;
	qd() {
		cost = 0;
	}
	void ins(pair<int, int> p) {
		qs.insert({p.first, {0, p.second}});
	}
	void merge(qd & oth) {
		int delta = oth.cost - cost;
		for(auto p : oth.qs) {
			qs.insert({p.first, {p.second.first + delta, p.second.second}});
		}
	}
	void sync(int i) {
		auto lim = qs.lower_bound({i + 1, {0, 0}});
		for(auto it = qs.begin(); it != lim; it = qs.erase(it)) {
			ans[it->second.second] = cost + it->second.first;
		}
	}
};
qd data[mx];
struct st {
	pair<int, int> best;
	st * l;
	st * r;
	int size;
	st() {}
	st(int sz, int i) {
		size = sz;
		if(size > 1) {
			l = new st(size/2, i);
			r = new st((size + 1)/2, i + (size/2));
			best = max(l->best, r->best);
		} else {
			best = {intervals[i].second, i};
		}
	}
	pair<int, int> get(int s, int e) { /* [l, r) */
		s = max(0, s);
		e = min(e, size);
		if(s == 0 && e == size) return best;
		pair<int, int> res = {0, 0};
		if(s < l->size) res = max(res, l->get(s, e));
		if(e > l->size) res = max(res, r->get(s - l->size, e - l->size));
		return res;
	}
};
st tree;
int get_idx(int i) {
	int a = 0;
	for(int delta = (1<<18); delta >= 1; delta >>= 1) {
		int tmp = a + delta;
		if(tmp >= n) continue;
		if(intervals[tmp].first <= i) a = tmp;
	}
	return a;
}
main() {
	for(int i = 0; i < mx; i++) ans[i] = -1;
	cin >> n >> q;
	vector<pair<int, int>> orig(n);
	for(int i = 0; i < n; i++) {
		int s, e; cin >> s >> e;
		orig[i] = {s, e};
		intervals[i] = {inf - e, inf - s};
	}
	vector<pair<pair<int, int>, int>> order(n);
	for(int i = 0; i < n; i++) {
		order[i] = {{intervals[i].first, intervals[i].second}, i};
	}
	sort(order.begin(), order.end());
	vector<int> pos(n);
	for(int i = 0; i < n; i++) {
		pos[order[i].second] = i;
	}
	for(int i = 0; i < q; i++) {
		int s, e; cin >> e >> s;
		if(s == e) {
			ans[i] = 0;
			continue;
		}
		if(orig[e - 1].second > orig[s - 1].first) continue;
		data[pos[s - 1]].ins({intervals[e - 1].first, i});
	}
	vector<pair<int, int>> tmp(n);
	for(int i = 0; i < n; i++) {
		tmp[i] = intervals[order[i].second];
	}
	for(int i = 0; i < n; i++) {
		intervals[i] = tmp[i];
	}
	tree = st(n, 0);
	for(int i = 0; i < n; i++) {
		int r = intervals[i].second;
		int dst_int = get_idx(r);
		data[i].cost++;
		data[i].sync(r);
		if(dst_int == i) continue;
		pair<int, int> next_best = tree.get(i + 1, dst_int + 1);
		int nidx = next_best.second;
		if(data[i].qs.size() > data[nidx].qs.size()) swap(data[i], data[nidx]);
		data[nidx].merge(data[i]);
	}
	for(int i = 0; i < q; i++) {
		if(ans[i] == -1) cout << "impossible" << endl;
		else cout << ans[i] << endl;
	}
}

Compilation message

events.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~
events.cpp: In function 'int main()':
events.cpp:93:3: error: reference to 'data' is ambiguous
   93 |   data[pos[s - 1]].ins({intervals[e - 1].first, i});
      |   ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:106:3: error: reference to 'data' is ambiguous
  106 |   data[i].cost++;
      |   ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:107:3: error: reference to 'data' is ambiguous
  107 |   data[i].sync(r);
      |   ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:111:6: error: reference to 'data' is ambiguous
  111 |   if(data[i].qs.size() > data[nidx].qs.size()) swap(data[i], data[nidx]);
      |      ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:111:26: error: reference to 'data' is ambiguous
  111 |   if(data[i].qs.size() > data[nidx].qs.size()) swap(data[i], data[nidx]);
      |                          ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:111:53: error: reference to 'data' is ambiguous
  111 |   if(data[i].qs.size() > data[nidx].qs.size()) swap(data[i], data[nidx]);
      |                                                     ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:111:62: error: reference to 'data' is ambiguous
  111 |   if(data[i].qs.size() > data[nidx].qs.size()) swap(data[i], data[nidx]);
      |                                                              ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:112:3: error: reference to 'data' is ambiguous
  112 |   data[nidx].merge(data[i]);
      |   ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~
events.cpp:112:20: error: reference to 'data' is ambiguous
  112 |   data[nidx].merge(data[i]);
      |                    ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from events.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
  319 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  310 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  300 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  290 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
events.cpp:31:4: note:                 'qd data [100005]'
   31 | qd data[mx];
      |    ^~~~