Submission #1267408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267408		ChuanChen	Palembang Bridges (APIO15_bridge)	C++20	Compilation error	0 ms	0 KiB

bridge

#include<bits/stdc++.h>
#define debug(v) //cerr << #v << ": " << v << '\n';
using namespace std;
#define int long long;
typedef pair<int, int> pii;
typedef long long ll;
int k, n;
ll ans;
vector<pii> inter;
bool cmp(pii a, pii b){
	return a.first+a.second < b.first+b.second;
}

struct two_set{
	multiset<int> s1, s2;
	//s1-> smaller than mid
	//s2 -> greater than mid;
	//s1.size() >= s2.size();
	ll sum1, sum2; 

	ll median(){
		if(s1.empty()){
			// cerr << "empty set\n";
			return 0;
		}
		return *s1.rbegin();
	}

	void add(int v){
		if(s1.empty()){
			s1.insert(v);
			sum1 += v;
			return;
		}

		if(s1.size() == s2.size()){
			if(v <= *s2.begin()){
				sum1 += v;
				s1.insert(v);
			}
			else{
				sum2 += v;
				s2.insert(v);

				sum1 += *s2.begin();
				s1.insert( *s2.begin() );

				sum2 -= *s2.begin();
				s2.erase(s2.begin());
			}
		}
		else{
			sum1 += v;
			s1.insert(v);

			sum2 += *(--s1.end());
			s2.insert( *(--s1.end()) );

			sum1 -= *(--s1.end());
			s1.erase( --s1.end() );
		}
	}

	void remove(int v){
		if(s1.size() == s2.size()){
			if(v < *s2.begin()){
				sum1 -= v;
				s1.erase(s1.find(v));

				sum1 += *s2.begin(); 
				s1.insert(*s2.begin());
				
				sum2 -= *s2.begin(); 
				s2.erase(s2.begin());
			}
			else{
				sum2 -= v;
				s2.erase(s2.find(v));
			}
		}
		else{
			if(v <= *s1.rbegin()){
				sum1 -= v;
				s1.erase(s1.find(v));
			}
			else{
				sum2 -= v;
				s2.erase(s2.find(v));

				sum2 += *(--s1.end()) ;
				s2.insert( *(--s1.end()) );

				sum1 -= *(--s1.end()) ;
				s1.erase( --s1.end() );
			}
		}
	}

	ll dist(){
		return s1.size()*median()-sum1 + sum2 - s2.size()*median();
	}
};
two_set esq, dir;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int k, n;
	cin >> k >> n;
	for(int i = 1; i <= n; i++){
		char za, zb; int a, b;
		cin >> za >> a >> zb >> b;
		if(a>b) swap(a, b);
		if(za==zb){
			ans += b-a;
		}
		else{
			ans++;
			inter.push_back({a, b});
		}
	}
	debug(ans)
	sort(inter.begin(), inter.end());

	for(auto[L, R] : inter){
		dir.add(L);
		dir.add(R);

		debug(L);
		debug(R);
		debug(dir.median());
		debug(dir.dist());
	}
	debug(dir.median());

	if(k == 1){
		cout << ans+dir.dist() << '\n';
		return 0;
	}

	ll best = 1e18;

	for(auto[L, R] : inter){
		dir.remove(L);
		dir.remove(R);
		esq.add(L);
		esq.add(R);

		debug(dir.median());
		debug(dir.dist());
		debug(esq.median());
		debug(esq.dist());
		debug(' ');

		best = min(best, dir.dist()+esq.dist());
	}
	debug(best)
	cout << ans+best << '\n';
}

Compilation message (stderr)

bridge.cpp:4:18: error: wrong number of template arguments (1, should be 2)
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:5:14: note: in expansion of macro 'int'
    5 | typedef pair<int, int> pii;
      |              ^~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from bridge.cpp:1:
/usr/include/c++/13/bits/stl_pair.h:187:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  187 |     struct pair
      |            ^~~~
bridge.cpp:5:1: warning: 'typedef' was ignored in this declaration
    5 | typedef pair<int, int> pii;
      | ^~~~~~~
bridge.cpp:5:17: error: expected unqualified-id before ',' token
    5 | typedef pair<int, int> pii;
      |                 ^
bridge.cpp:4:13: error: expected unqualified-id before 'long'
    4 | #define int long long;
      |             ^~~~
bridge.cpp:5:19: note: in expansion of macro 'int'
    5 | typedef pair<int, int> pii;
      |                   ^~~
bridge.cpp:5:22: error: expected unqualified-id before '>' token
    5 | typedef pair<int, int> pii;
      |                      ^
bridge.cpp:4:18: error: declaration does not declare anything [-fpermissive]
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:7:1: note: in expansion of macro 'int'
    7 | int k, n;
      | ^~~
bridge.cpp:7:5: error: 'k' does not name a type
    7 | int k, n;
      |     ^
bridge.cpp:9:8: error: 'pii' was not declared in this scope
    9 | vector<pii> inter;
      |        ^~~
bridge.cpp:9:11: error: template argument 1 is invalid
    9 | vector<pii> inter;
      |           ^
bridge.cpp:9:11: error: template argument 2 is invalid
bridge.cpp:10:10: error: 'pii' was not declared in this scope
   10 | bool cmp(pii a, pii b){
      |          ^~~
bridge.cpp:10:17: error: 'pii' was not declared in this scope
   10 | bool cmp(pii a, pii b){
      |                 ^~~
bridge.cpp:10:22: error: expression list treated as compound expression in initializer [-fpermissive]
   10 | bool cmp(pii a, pii b){
      |                      ^
bridge.cpp:4:18: error: template argument 1 is invalid
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:15:18: note: in expansion of macro 'int'
   15 |         multiset<int> s1, s2;
      |                  ^~~
bridge.cpp:4:18: error: template argument 2 is invalid
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:15:18: note: in expansion of macro 'int'
   15 |         multiset<int> s1, s2;
      |                  ^~~
bridge.cpp:4:18: error: template argument 3 is invalid
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:15:18: note: in expansion of macro 'int'
   15 |         multiset<int> s1, s2;
      |                  ^~~
bridge.cpp:15:21: error: expected unqualified-id before '>' token
   15 |         multiset<int> s1, s2;
      |                     ^
bridge.cpp:4:22: error: expected ')' before ';' token
    4 | #define int long long;
      |                      ^
bridge.cpp:29:18: note: in expansion of macro 'int'
   29 |         void add(int v){
      |                  ^~~
bridge.cpp:29:17: note: to match this '('
   29 |         void add(int v){
      |                 ^
bridge.cpp:29:22: error: 'v' does not name a type
   29 |         void add(int v){
      |                      ^
bridge.cpp:4:22: error: expected ')' before ';' token
    4 | #define int long long;
      |                      ^
bridge.cpp:64:21: note: in expansion of macro 'int'
   64 |         void remove(int v){
      |                     ^~~
bridge.cpp:64:20: note: to match this '('
   64 |         void remove(int v){
      |                    ^
bridge.cpp:64:25: error: 'v' does not name a type
   64 |         void remove(int v){
      |                         ^
bridge.cpp: In member function 'll two_set::median()':
bridge.cpp:22:20: error: 's1' was not declared in this scope; did you mean 'y1'?
   22 |                 if(s1.empty()){
      |                    ^~
      |                    y1
bridge.cpp:26:25: error: 's1' was not declared in this scope; did you mean 'y1'?
   26 |                 return *s1.rbegin();
      |                         ^~
      |                         y1
bridge.cpp: In member function 'll two_set::dist()':
bridge.cpp:100:24: error: 's1' was not declared in this scope; did you mean 'y1'?
  100 |                 return s1.size()*median()-sum1 + sum2 - s2.size()*median();
      |                        ^~
      |                        y1
bridge.cpp:100:57: error: 's2' was not declared in this scope; did you mean 'sum2'?
  100 |                 return s1.size()*median()-sum1 + sum2 - s2.size()*median();
      |                                                         ^~
      |                                                         sum2
bridge.cpp: In function 'int main()':
bridge.cpp:4:18: error: declaration does not declare anything [-fpermissive]
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:107:9: note: in expansion of macro 'int'
  107 |         int k, n;
      |         ^~~
bridge.cpp:107:13: error: 'k' was not declared in this scope
  107 |         int k, n;
      |             ^
bridge.cpp:107:16: error: 'n' was not declared in this scope; did you mean 'yn'?
  107 |         int k, n;
      |                ^
      |                yn
bridge.cpp:4:18: error: declaration does not declare anything [-fpermissive]
    4 | #define int long long;
      |                  ^~~~
bridge.cpp:109:13: note: in expansion of macro 'int'
  109 |         for(int i = 1; i <= n; i++){
      |             ^~~
bridge.cpp:109:17: error: 'i' was not declared in this scope
  109 |         for(int i = 1; i <= n; i++){
      |                 ^
bridge.cpp:109:30: error: expected ')' before ';' token
  109 |         for(int i = 1; i <= n; i++){
      |            ~                 ^
      |                              )
bridge.cpp:109:32: error: 'i' was not declared in this scope
  109 |         for(int i = 1; i <= n; i++){
      |                                ^
bridge.cpp:122:20: error: request for member 'begin' in 'inter', which is of non-class type 'int'
  122 |         sort(inter.begin(), inter.end());
      |                    ^~~~~
bridge.cpp:122:35: error: request for member 'end' in 'inter', which is of non-class type 'int'
  122 |         sort(inter.begin(), inter.end());
      |                                   ^~~
bridge.cpp:124:26: error: 'begin' was not declared in this scope
  124 |         for(auto[L, R] : inter){
      |                          ^~~~~
bridge.cpp:124:26: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
In file included from /usr/include/c++/13/bits/ranges_algobase.h:38,
                 from /usr/include/c++/13/bits/ranges_algo.h:38,
                 from /usr/include/c++/13/algorithm:63:
/usr/include/c++/13/bits/ranges_base.h:489:44: note:   'std::ranges::__cust::begin'
  489 |     inline constexpr __cust_access::_Begin begin{};
      |                                            ^~~~~
In file included from /usr/include/c++/13/filesystem:50,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:200:
/usr/include/c++/13/bits/fs_dir.h:607:3: note:   'std::filesystem::__cxx11::begin'
  607 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
In file included from /usr/include/c++/13/bits/stl_iterator_base_types.h:71,
                 from /usr/include/c++/13/bits/stl_algobase.h:65:
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note:   'std::ranges::__cust_access::begin'
  984 |     void begin(const auto&) = delete;
      |          ^~~~~
bridge.cpp:124:26: error: 'end' was not declared in this scope
  124 |         for(auto[L, R] : inter){
      |                          ^~~~~
bridge.cpp:124:26: note: suggested alternatives:
/usr/include/c++/13/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note:   'std::ranges::__cust::end'
  490 |     inline constexpr __cust_access::_End end{};
      |                                          ^~~
/usr/include/c++/13/bits/fs_dir.h:612:3: note:   'std::filesystem::__cxx11::end'
  612 |   end(recursive_directory_iterator) noexcept
      |   ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note:   'std::ranges::__cust_access::end'
  137 |     void end(const auto&) = delete;
      |          ^~~
bridge.cpp:142:26: error: 'begin' was not declared in this scope
  142 |         for(auto[L, R] : inter){
      |                          ^~~~~
bridge.cpp:142:26: note: suggested alternatives:
/usr/include/c++/13/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
/usr/include/c++/13/bits/ranges_base.h:489:44: note:   'std::ranges::__cust::begin'
  489 |     inline constexpr __cust_access::_Begin begin{};
      |                                            ^~~~~
/usr/include/c++/13/bits/fs_dir.h:607:3: note:   'std::filesystem::__cxx11::begin'
  607 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
/usr/include/c++/13/bits/iterator_concepts.h:984:10: note:   'std::ranges::__cust_access::begin'
  984 |     void begin(const auto&) = delete;
      |          ^~~~~
bridge.cpp:142:26: error: 'end' was not declared in this scope
  142 |         for(auto[L, R] : inter){
      |                          ^~~~~
bridge.cpp:142:26: note: suggested alternatives:
/usr/include/c++/13/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note:   'std::ranges::__cust::end'
  490 |     inline constexpr __cust_access::_End end{};
      |                                          ^~~
/usr/include/c++/13/bits/fs_dir.h:612:3: note:   'std::filesystem::__cxx11::end'
  612 |   end(recursive_directory_iterator) noexcept
      |   ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note:   'std::ranges::__cust_access::end'
  137 |     void end(const auto&) = delete;
      |          ^~~