Submission #672460

#	Time	Username	Problem	Language	Result	Execution time	Memory
672460		Eae02	Aliens (IOI16_aliens)	C++17	Compilation error	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.

aliens

    #include "aliens.h"
     
    #include <bits/stdc++.h>
    using namespace std;
    using ll = __int128_t;
    #define all(x) begin(x),end(x)
     
    struct Line {
    	mutable ll k, m, p;
    	ll howManyPhotos;
    	bool operator<(const Line& o) const { return k < o.k; }
    	bool operator<(ll x) const { return p < x; }
    };
    struct LineContainer : multiset<Line, less<>> {
    	const ll inf = LLONG_MAX;
    	ll div(ll a, ll b) { // floored division
    		return a / b - ((a ^ b) < 0 && a % b);
    	}
    	bool isect(iterator x, iterator y) {
    		if (y == end()) { x->p = inf; return false; }
    		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
    		else x->p = div(y->m - x->m, x->k - y->k);
    		return x->p >= y->p;
    	}
    	void add(ll k, ll m, ll howManyPhotos) {
    		auto z = insert({k, m, 0, howManyPhotos}), y = z++, x = y;
    		while (isect(y, z)) z = erase(z);
    		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    	}
    	pair<ll, ll> query(ll x) { assert(!empty());
    		auto l = *lower_bound(x);
    		return make_pair(l.k * x + l.m, l.howManyPhotos);
    	}
    };
     
    long long take_photos(int n, int m, int K, vector<int> r, vector<int> c) {
    	vector<pair<ll, ll>> intvs;
    	for (int i = 0; i < n; i++) {
    		intvs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
    	}
    	sort(all(intvs));
    	
    	vector<pair<ll, ll>> st;
    	for (auto [l, r] : intvs) {
    		if (st.empty() || -r > st.back().second)
    			st.emplace_back(l, -r);
    	}
    	
    	//for (auto [l, r] : st) {
    	//	cerr << "intv " << l << " " << r << "\n";
    	//}
    	
    	auto square = [&] (ll x) { return x * x; };
    	
    	auto alienTrick = [&] (ll cost) -> pair<ll, ll> { // (ans, howManyPhotos)
    		vector<pair<ll, ll>> dp(st.size() + 1);
    		dp[st.size()] = {0,0};
    		LineContainer lc;
    		auto addToLC = [&] (ll ie) {
    			if (ie == 0) return;
    			ll ex = st[ie-1].second + 1;
    			ll bx = st[ie].first;
    			ll k = -2 * ex;
    			ll m =
    				dp[ie].first
    				+ square(ex)
    				- square(max(ex - bx, (ll)0LL));
    			lc.add(-k, -m, dp[ie].second);
    		};
    		for (ll i = (ll)st.size() - 1; i >= 0; i--) {
    			pair<ll, ll> ans = {
    				dp[st.size()].first + square(st.back().second - st[i].first + 1) + cost,
    				-1LL
    			};
    			/*for (ll ie = i + 1; ie < (ll)st.size(); ie++) {
    				ll ex = st[ie-1].second + 1;
    				ll bx = st[ie].first;
    				ans = min(ans,
    					dp[ie][remk - 1]
    					+ square(ex)
    					- 2 * ex * st[i].first
    					+ square(st[i].first)
    					- square(max(ex - bx, 0LL))
    				);
    			}*/
    			if (!lc.empty()) {
    				auto lcq = lc.query(st[i].first);
    				ans = min(ans, make_pair(-lcq.first + square(st[i].first) + cost, lcq.second - 1));
    			}
    			dp[i] = ans;
    			addToLC(i);
    		}
    		return { dp[0].first, -dp[0].second };
    	};
    	
    	ll lo = 0;
    	ll hi = 1E9;
    	while (hi > lo) {
    		ll mid = lo + (hi - lo) / 2;
    		auto [ans, howManyPhotos] = alienTrick(mid);
    		if (howManyPhotos > K)
    			lo = mid + 1;
    		else
    			hi = mid;
    	}
    	auto [ans, howManyPhotos] = alienTrick(lo);
    	return ans - lo * K;
    }

Compilation message (stderr)

aliens.cpp:2:5: error: extended character   is not valid in an identifier
    2 |      
      |     ^
aliens.cpp:7:5: error: extended character   is not valid in an identifier
    7 |      
      |     ^
aliens.cpp:36:5: error: extended character   is not valid in an identifier
   36 |      
      |     ^
aliens.cpp:2:5: error: '\U000000a0' does not name a type
    2 |      
      |     ^
aliens.cpp:7:5: error: '\U000000a0' does not name a type
    7 |      
      |     ^
aliens.cpp:14:37: error: 'Line' was not declared in this scope
   14 |     struct LineContainer : multiset<Line, less<>> {
      |                                     ^~~~
aliens.cpp:14:48: error: template argument 1 is invalid
   14 |     struct LineContainer : multiset<Line, less<>> {
      |                                                ^~
aliens.cpp:14:48: error: template argument 3 is invalid
aliens.cpp:19:17: error: 'auto' parameter not permitted in this context
   19 |      bool isect(iterator x, iterator y) {
      |                 ^~~~~~~~
aliens.cpp:19:29: error: 'auto' parameter not permitted in this context
   19 |      bool isect(iterator x, iterator y) {
      |                             ^~~~~~~~
aliens.cpp: In member function 'bool LineContainer::isect()':
aliens.cpp:20:11: error: 'y' was not declared in this scope; did you mean 'yn'?
   20 |       if (y == end()) { x->p = inf; return false; }
      |           ^
      |           yn
aliens.cpp:20:20: error: no matching function for call to 'end()'
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/bits/stl_vector.h:63,
                 from /usr/include/c++/10/vector:67,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
  101 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/10/initializer_list:101:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  100 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
 1234 |     end(valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1234:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1244:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
aliens.cpp:20:25: error: 'x' was not declared in this scope
   20 |       if (y == end()) { x->p = inf; return false; }
      |                         ^
aliens.cpp:21:11: error: 'x' was not declared in this scope
   21 |       if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |           ^
aliens.cpp:21:19: error: 'y' was not declared in this scope; did you mean 'yn'?
   21 |       if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                   ^
      |                   yn
aliens.cpp:23:14: error: 'x' was not declared in this scope
   23 |       return x->p >= y->p;
      |              ^
aliens.cpp:23:22: error: 'y' was not declared in this scope; did you mean 'yn'?
   23 |       return x->p >= y->p;
      |                      ^
      |                      yn
aliens.cpp: In member function 'void LineContainer::add(ll, ll, ll)':
aliens.cpp:26:16: error: 'insert' was not declared in this scope; did you mean 'isect'?
   26 |       auto z = insert({k, m, 0, howManyPhotos}), y = z++, x = y;
      |                ^~~~~~
      |                isect
aliens.cpp:27:20: error: 'y' was not declared in this scope; did you mean 'yn'?
   27 |       while (isect(y, z)) z = erase(z);
      |                    ^
      |                    yn
aliens.cpp:27:31: error: 'erase' was not declared in this scope
   27 |       while (isect(y, z)) z = erase(z);
      |                               ^~~~~
aliens.cpp:28:11: error: 'x' was not declared in this scope
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |           ^
aliens.cpp:28:22: error: no matching function for call to 'begin()'
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/bits/stl_vector.h:63,
                 from /usr/include/c++/10/vector:67,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1214:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1224:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
aliens.cpp:28:38: error: 'y' was not declared in this scope; did you mean 'yn'?
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                      ^
      |                                      yn
aliens.cpp:28:55: error: 'erase' was not declared in this scope
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                                       ^~~~~
aliens.cpp:29:15: error: 'y' was not declared in this scope; did you mean 'yn'?
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |               ^
      |               yn
aliens.cpp:29:19: error: 'x' was not declared in this scope
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                   ^
aliens.cpp:29:31: error: no matching function for call to 'begin()'
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/bits/stl_vector.h:63,
                 from /usr/include/c++/10/vector:67,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1214:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1224:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
aliens.cpp:29:63: error: 'erase' was not declared in this scope
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                                                               ^~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from aliens.cpp:3:
aliens.cpp: In member function 'std::pair<__int128, __int128> LineContainer::query(ll)':
aliens.cpp:31:47: error: no matching function for call to 'empty()'
   31 |      pair<ll, ll> query(ll x) { assert(!empty());
      |                                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:263:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  263 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:263:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from aliens.cpp:3:
aliens.cpp:31:47: note:   candidate expects 1 argument, 0 provided
   31 |      pair<ll, ll> query(ll x) { assert(!empty());
      |                                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:272:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  272 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:272:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_6