oj.uz

답안 #1053621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053621 2024-08-11T14:31:10 Z _rain_ Palembang Bridges (APIO15_bridge) C++14
22 / 100
 47 ms 8884 KB 
#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 = (valuex.size()>0?(i64)1e18 : 0);
		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;
	assert(k==1);
	// 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: 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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2524 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 15 ms 7112 KB Output is correct
13 Correct 47 ms 8884 KB Output is correct
14 Correct 28 ms 7112 KB Output is correct
15 Correct 27 ms 6092 KB Output is correct
16 Correct 19 ms 8140 KB Output is correct
17 Correct 29 ms 8640 KB Output is correct
18 Correct 40 ms 8388 KB Output is correct
19 Correct 44 ms 8656 KB Output is correct
20 Correct 19 ms 8128 KB Output is correct
21 Correct 43 ms 8384 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4696 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -