Submission #1053613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053613	2024-08-11T14:20:58 Z	_rain_	Palembang Bridges (APIO15_bridge)	C++17	Compilation error	0 ms	0 KB

bridge

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define prev t1vodich
#define prefix orzhehe

const int maxn = 1e5;
i64 prev1[maxn+2] , suf1[maxn+2];
i64 prev2[maxn+2] , suf2[maxn+2];
int n , k;

struct Point
{
	char zone1 , zone2;
	int p1 , p2;
	void read()
	{
		cin>>zone1>>p1>>zone2>>p2;
		if (p1>p2) {
			swap(p1,p2);
			swap(zone1,zone2);
		}
		return;
	}
};
Point point[maxn+2];

namespace subtask1
{
	bool check()
	{
		return k == 1;
	}
	vector<int> v1 , v2;
		i64 prefixA(int l , int r)
			{
				if (l>r) return 0;
				return prev1[r] - prev1[l - 1];
			}
		i64 prefixB(int l , int r)
			{
				if (l>r) return 0;
				return prev2[r] - prev2[l - 1];
			}
		i64 sufA(int l , int r)
			{
				if (l>r) return 0;
				return suf1[l] - suf1[r+1];
			}
		i64 sufB(int l , int r)
			{
				if (l>r) return 0;
				return suf2[l] - suf2[r+1];
			}
		i64 length(int l , int r)
		{
			if (l>r) return 0;
			return r - l + 1;
		}
	i64 getA(int x)
	{
		int xx = upper_bound(v1.begin(),v1.end(),x) - v1.begin() - 1;
		int nwn = v1.size()-1;
		return (i64)x * length(1,xx) - prefixA(1 , xx) + sufA(xx+1,nwn) - (i64)x * length(xx+1,nwn);
	}
	i64 getB(int x)
	{
		int xx = upper_bound(v2.begin(),v2.end(),x) - v2.begin() - 1;
		int nwn = v2.size()-1;
		return (i64)x * length(1,xx) - prefixB(1 , xx) + sufB(xx+1,nwn) - (i64)x * length(xx+1,nwn);
	}

	void main_code()
	{
		vector<int> valuex;
		v1.push_back(-1); v2.push_back(-1);	
		i64 answer = 0;
		for (int i = 1; i <= n; ++i)
		{
			if (point[i].zone1==point[i].zone2)
				answer += point[i].p2 - point[i].p1;
			else {
				if (point[i].zone1=='A') v1.push_back(point[i].p1); else v2.push_back(point[i].p1);
				if (point[i].zone2=='A') v1.push_back(point[i].p2); else v2.push_back(point[i].p2);
				valuex.push_back(point[i].p1);
				valuex.push_back(point[i].p2);
			}
			// cout << point[i].zone1 << ' ' << point[i].p1 << ' ' << point[i].zone2 << ' ' << point[i].p2 << '\n';
		}
		sort(valuex.begin(),valuex.end()); valuex.resize(unique(valuex.begin(),valuex.end())-valuex.begin());
		sort(v1.begin(),v1.end());
		sort(v2.begin(),v2.end());
		for (int i = 1; i < v1.size(); ++i)
			prev1[i]=prev1[i-1]+v1[i];
		for (int i = v1.size()-1; i >= 1; --i)
			suf1[i]=suf1[i+1]+v1[i];
		for (int i = 1; i < v2.size(); ++i)
			prev2[i]=prev2[i-1]+v2[i];
		for (int i = v2.size()-1;i >= 1; --i)
			suf2[i]=suf2[i+1]+v2[i];
		i64 addmore = (i64)1e18;
		for (auto& x : valuex)
		{
			addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
			// cout << x << ' ' << getA(x) + getB(x) + v1.size() - 1 << '\n';;
		}
		cout << addmore + answer << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r"))
	{
		freopen(name".inp","r",stdin);
		freopen(name".out","w",stdout);
	}
	cin >> k >> n;
	for (int i = 1; i <= n; ++i) point[i].read();
	if (subtask1::check()) return subtask1::main_code(),0;
	// if (subtask2::check()) return subtask2::main_code(),0;
}

Compilation message

bridge.cpp: In function 'void subtask1::main_code()':
bridge.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int i = 1; i < v1.size(); ++i)
      |                   ~~^~~~~~~~~~~
bridge.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i = 1; i < v2.size(); ++i)
      |                   ~~^~~~~~~~~~~
bridge.cpp:104:61: error: no matching function for call to 'min(i64&, long long unsigned int)'
  104 |    addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
      |                                                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
bridge.cpp:104:61: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long long unsigned int')
  104 |    addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
      |                                                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
bridge.cpp:104:61: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long long unsigned int')
  104 |    addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
      |                                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
bridge.cpp:104:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  104 |    addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
      |                                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
bridge.cpp:104:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  104 |    addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
      |                                                             ^
bridge.cpp: In function 'int main()':
bridge.cpp:118:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   freopen(name".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:119:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   freopen(name".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~