답안 #33633 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33633	2017-10-31T02:57:37 Z	sinhriv	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2000 ms	9152 KB

bridge

#include <bits/stdc++.h>

using namespace std;

struct Point{
	int x;
	int y;

	void read(){
		char read[5];
		scanf("%s%d", read, &y);
		x = (read[0] - 'A');
	}
};	

struct Person{
	Point u;
	Point v;

	bool check(){
		u.read();
		v.read();
		return (u.x == v.x);
	}

	int calc(int val){
		return abs(u.y - val) + abs(v.y - val);
	}
};

vector < pair < int, int > > a;

long long One(){
	if(a.size() == 0) return 0;
	int n = a.size();
	vector < int > lst;

	for(int i = 0; i < n; ++i){
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);
	}

	sort(lst.begin(), lst.end());

	long long ans = 0;


	for(int i = 0; i < n + n; ++i){
		ans += abs(lst[i] - lst[n]);
	}
	return ans + n; 
}

struct lex_compare {
  bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
  	if(x.first + x.second == y.first + y.second) {
  		if(x.first == y.first) return x.second < y.second;
  		return x.first < y.first;
  	}
  	return x.first + x.second < y.first + y.second;
  }
};


struct second_compare {
  bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
  	if(x.second != y.second) return x.second  < y.second;
  	return x.first < y.first;
  }
};

const int N = 2e5 + 10;

long long prefix[N];

int calc(pair < int, int > p, int val){
	return abs(p.first - val) + abs(p.second - val);
}

long long Two(){
	int n = a.size();
	if(n == 0) return 0;

	vector < int > lst;

	for(int i = 0; i < n; ++i){
		if(a[i].first > a[i].second){
			swap(a[i].first, a[i].second);
		}
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);

	}

	sort(a.begin(), a.end());
	sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());

	for(int i = 0; i < n; ++i){
		prefix[i] = a[i].first + a[i].second;
		if(i > 0) prefix[i] += prefix[i - 1];
	}

	int small = 0;

	long long sum = 0;
	long long total = 0;
	
	long long ans = 1e18;

	multiset < int > tree;



	for(int i = 0; i < lst.size(); ++i){
		int x = lst[i];
		while(small < n && a[small].first <= x){
			sum += a[small].second;
			total += a[small].first;
			tree.insert(a[small].second);
			++small;
		}
		while(!tree.empty() && *tree.begin() <= x){
			sum -= *tree.begin() * 2;
			tree.erase(tree.begin());
		}


		long long now = (1LL * small * x - total) + (sum + 1LL * (small - 2LL * tree.size()) * x);
	
		multiset < pair < int, int >, lex_compare > inside;	
		multiset < pair < int, int >, second_compare > big;
		
		long long sumBigX = 0;
		long long sumBigY = 0;
		long long sumInsideX = 0;
		long long sumInsideY = 0;
		long long sumOutside = 0;

		int pter = small;		
		for(int j = i + 1; j < lst.size(); ++j){
			int y = lst[j];
			int where = lower_bound(a.begin(), a.end(), make_pair(y, 0)) - a.begin();

			long long most = prefix[n - 1] - (where > 0 ? prefix[where - 1] : 0) - 2LL * (n - where) * y;

			
			while(pter < where){
				if(a[pter].second >= y){
					big.insert(a[pter]);
					sumBigX += a[pter].first;
					sumBigY += a[pter].second;
				}
				else{
					inside.insert(a[pter]);
					sumInsideX += a[pter].first;
					sumInsideY += a[pter].second;
				}
				++pter;
			}
			
			while(!big.empty() && big.begin() -> second < y){
				sumBigX -= big.begin() -> first;
				sumBigY -= big.begin() -> second;


				sumInsideX += big.begin() -> first;
				sumInsideY += big.begin() -> second;
				inside.insert(*big.begin());
				big.erase(big.begin());
			}

			while(!inside.empty()){
				auto p = *inside.begin();
				if(p.first + p.second <= x + y){
					sumInsideX -= p.first;
					sumInsideY -= p.second;
					sumOutside += calc(p, x);
					inside.erase(inside.begin());
					continue;
				}
				break; 
			}
			ans = min(ans, 2LL * int(inside.size()) * y - sumInsideY - sumInsideX + sumOutside + sumBigY - sumBigX + most + now);
     
		}
	}


	return n + ans;
}

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	long long out = 0;

	int k, n;
	scanf("%d%d", &k, &n);

	for(int i = 1; i <= n; ++i){
		Person x;
		if(x.check()){
			out += x.calc(x.u.y);
		}
		else{
			a.emplace_back(x.u.y, x.v.y);
		}
	}


	if(k == 1) cout << One() + out;
	else{
		cout << min(One(), Two()) + out;
	}
	return 0;
}

Compilation message

bridge.cpp: In function 'long long int Two()':
bridge.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lst.size(); ++i){
                   ^
bridge.cpp:141:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < lst.size(); ++j){
                        ^
bridge.cpp: In function 'int main()':
bridge.cpp:195:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
bridge.cpp:201:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &n);
                       ^
bridge.cpp: In member function 'void Point::read()':
bridge.cpp:11:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d", read, &y);
                          ^

Subtask #1
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	3588 KB	Output is correct
2	Correct	3588 KB	Output is correct
3	Correct	3588 KB	Output is correct
4	Correct	3588 KB	Output is correct
5	Correct	3588 KB	Output is correct
6	Correct	3588 KB	Output is correct
7	Correct	3588 KB	Output is correct
8	Correct	3588 KB	Output is correct
9	Correct	3588 KB	Output is correct
10	Correct	3588 KB	Output is correct
11	Correct	3588 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3588 KB	Output is correct
2	Correct	0 ms	3588 KB	Output is correct
3	Correct	0 ms	3588 KB	Output is correct
4	Correct	0 ms	3588 KB	Output is correct
5	Correct	0 ms	3588 KB	Output is correct
6	Correct	0 ms	3588 KB	Output is correct
7	Correct	0 ms	3588 KB	Output is correct
8	Correct	0 ms	3588 KB	Output is correct
9	Correct	0 ms	3588 KB	Output is correct
10	Correct	0 ms	3588 KB	Output is correct
11	Correct	0 ms	3588 KB	Output is correct
12	Correct	29 ms	6744 KB	Output is correct
13	Correct	59 ms	6744 KB	Output is correct
14	Correct	56 ms	6744 KB	Output is correct
15	Correct	43 ms	5208 KB	Output is correct
16	Correct	29 ms	6744 KB	Output is correct
17	Correct	49 ms	6744 KB	Output is correct
18	Correct	49 ms	6744 KB	Output is correct
19	Correct	59 ms	6744 KB	Output is correct
20	Correct	39 ms	6744 KB	Output is correct
21	Correct	66 ms	6744 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3588 KB	Output is correct
2	Correct	0 ms	3588 KB	Output is correct
3	Correct	0 ms	3588 KB	Output is correct
4	Correct	0 ms	3588 KB	Output is correct
5	Correct	0 ms	3588 KB	Output is correct
6	Correct	0 ms	3588 KB	Output is correct
7	Correct	0 ms	3588 KB	Output is correct
8	Correct	0 ms	3588 KB	Output is correct
9	Correct	0 ms	3588 KB	Output is correct
10	Correct	0 ms	3588 KB	Output is correct
11	Correct	0 ms	3588 KB	Output is correct
12	Correct	0 ms	3588 KB	Output is correct
13	Correct	0 ms	3588 KB	Output is correct
14	Correct	9 ms	3588 KB	Output is correct
15	Correct	313 ms	3588 KB	Output is correct
16	Correct	0 ms	3588 KB	Output is correct
17	Correct	3 ms	3588 KB	Output is correct
18	Correct	39 ms	3588 KB	Output is correct
19	Correct	0 ms	3720 KB	Output is correct
20	Correct	316 ms	3588 KB	Output is correct
21	Correct	219 ms	3720 KB	Output is correct
22	Correct	323 ms	3588 KB	Output is correct
23	Correct	0 ms	3588 KB	Output is correct
24	Correct	306 ms	3588 KB	Output is correct

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3588 KB	Output is correct
2	Correct	0 ms	3588 KB	Output is correct
3	Correct	0 ms	3588 KB	Output is correct
4	Correct	3 ms	3588 KB	Output is correct
5	Correct	0 ms	3588 KB	Output is correct
6	Correct	0 ms	3588 KB	Output is correct
7	Correct	0 ms	3588 KB	Output is correct
8	Correct	3 ms	3588 KB	Output is correct
9	Correct	0 ms	3588 KB	Output is correct
10	Correct	0 ms	3588 KB	Output is correct
11	Correct	0 ms	3588 KB	Output is correct
12	Correct	0 ms	3588 KB	Output is correct
13	Correct	0 ms	3588 KB	Output is correct
14	Correct	9 ms	3588 KB	Output is correct
15	Correct	313 ms	3588 KB	Output is correct
16	Correct	0 ms	3588 KB	Output is correct
17	Correct	3 ms	3588 KB	Output is correct
18	Correct	36 ms	3588 KB	Output is correct
19	Correct	0 ms	3720 KB	Output is correct
20	Correct	306 ms	3588 KB	Output is correct
21	Correct	199 ms	3720 KB	Output is correct
22	Correct	283 ms	3588 KB	Output is correct
23	Correct	0 ms	3588 KB	Output is correct
24	Correct	289 ms	3588 KB	Output is correct
25	Correct	53 ms	9152 KB	Output is correct
26	Correct	1576 ms	9152 KB	Output is correct
27	Execution timed out	2000 ms	8756 KB	Execution timed out
28	Halted	0 ms	0 KB	-

답안 #33633

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
0 / 37.0