Submission #1053617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053617		_rain_	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	2396 KiB

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)
		{
			i64 xx = getA(x) + getB(x) + v1.size() - 1;
			addmore = min(addmore , xx);
		}
		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 (stderr)

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: 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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37