Submission #1136359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136359		raspy	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

const int64_t inf = 10e10;

struct line
{
	int64_t c, m;
	line(int64_t _c, int64_t _m) {c = _c;m=_m;}
	int64_t operator()(int64_t x)
	{
		return c+m*x;
	}
	bool inter_ear(line l, line l1)
	{
		return (double)(c-l1.c)/(l1.m-m) < (double)(c-l.c)/(l.m-m);
	}
};

struct CHT
{
	deque<line> dq;
	deque<int64_t> pr;
	CHT() {dq = deque<line>();pr=deque<int64_t>();}
	void add(line l, int64_t k)
	{
		while (dq.size() > 1 && dq[dq.size()-2].inter_ear(dq.back(), l))
		{
			dq.pop_back();
			pr.pop_back();
		}
		dq.push_back(l);
		pr.push_back(k);
	}
	pair<int64_t, int64_t> get_best(int64_t x)
	{
		while (dq.size() > 1 && dq[1](x) < dq[0](x))
		{
			dq.pop_front();
			pr.pop_front();
		}
		return {dq[0](x), pr[0]};
	}
};

int64_t sq(int64_t x)
{
	return x*x;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
	// get rid of unimportant points
	for (long long i = 0; i < n; i++)
	{
		if (r[i] > c[i]) swap(r[i], c[i]);
		pnts.push_back({r[i], c[i]});
	}
	sort((pnts).begin(), pnts.end(), [](pair<long long, long long> pr, pair<long long, long long> dr){
		if (pr.first != dr.first) return pr < dr;
		return pr > dr;
	}); // sort them by increasing row and decreasing column nummber
	vector<pair<long long, long long>> a; // save only important points
	a.push_back(pnts[0]);
	for (long long i = 1; i < n; i++)
	{
		if (a.back().second < pnts[i].second)
			a.push_back(pnts[i]);
	}	//lambda optimization
	int64_t l = -1, d = 1e13;
	CHT ch;
	vector<pair<int64_t, int64_t>> dp;
	while (l+1 < d)
	{
		int64_t lamb = (l+d)/2;
		ch = CHT();
		dp = vector<pair<int64_t, int64_t>>(a.size());
		ch.add(line(sq(a[0].first)-2*a[0].first+1+lamb, -2*a[0].first), 0);
		for (int64_t i = 0; i < a.size(); i++)
		{
			auto [x, tk] = ch.get_best(a[i].second);
			x+=sq(a[i].second)+2*a[i].second;
			dp[i] = {x, tk+1};
			if (i==n-1) break;
			ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
		}
		if (dp.back().second <= k)
			d = lamb;
		else
			l = lamb;
	}
	int64_t lamb = d;
	ch = CHT();
	dp = vector<pair<int64_t, int64_t>>(a.size());
	ch.add(line(sq(a[0].first-1)+lamb, -2*a[0].first), 0);
	for (int64_t i = 0; i < a.size(); i++)
	{
		auto [x, tk] = ch.get_best(a[i].second);
		x+=sq(a[i].second)+2*a[i].second;
		dp[i] = {x, tk+1};
		if (i==n-1) break;
		ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
	}
	return dp.back().first-d*k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:59:17: error: 'pnts' was not declared in this scope; did you mean 'puts'?
   59 |                 pnts.push_back({r[i], c[i]});
      |                 ^~~~
      |                 puts
aliens.cpp:61:15: error: 'pnts' was not declared in this scope; did you mean 'puts'?
   61 |         sort((pnts).begin(), pnts.end(), [](pair<long long, long long> pr, pair<long long, long long> dr){
      |               ^~~~
      |               puts
aliens.cpp:87:45: error: no matching function for call to 'max(int64_t, long long int)'
   87 |                         ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
aliens.cpp:87:45: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   87 |                         ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
aliens.cpp:87:45: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   87 |                         ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
aliens.cpp:87:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   87 |                         ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
aliens.cpp:87:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   87 |                         ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:104:37: error: no matching function for call to 'max(int64_t, long long int)'
  104 |                 ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
aliens.cpp:104:37: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
  104 |                 ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
aliens.cpp:104:37: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
  104 |                 ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
aliens.cpp:104:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  104 |                 ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
aliens.cpp:104:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
  104 |                 ch.add(line(x-sq(max((int64_t)0, a[i].second-a[i+1].first+1))+sq(a[i+1].first-1)+lamb, -2*a[i+1].first), tk+1);
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~