답안 #45535 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45535	2018-04-15T06:52:41 Z	gnoor	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	341 ms	34688 KB

bridge

#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;

pair<int,int> ei[100100];
long long tmp[100100];

template <typename T,typename U>
long long work(T first, T last, U op) {
	op(first,0);
	multiset<int> ms;
	multiset<int>::iterator mid;
	
	ms.insert(first->first);
	ms.insert(first->second);
	mid = ms.begin();

	long long sum=first->second-first->first;
	op(++first,sum);

	while (first!=last) {
		ms.insert(first->first);
		ms.insert(first->second);
		sum+=abs(*mid-first->first);
		sum+=abs(*mid-first->second);

		if (first->second<*mid) {
			mid--;
		} else if (first->first>=*mid) {
			sum+=*mid*2;
			mid++;
			sum-=*mid*2;
		}
		op(++first,sum);
	}
	return sum;
}


int main () {
	int k,n;
	scanf("%d%d",&k,&n);
	char a,b;
	int x,y;
	long long ans=0;	
	int sz=0;
	for (int i=0;i<n;i++) {
		scanf(" %c%d %c%d",&a,&x,&b,&y);
		if (a==b) {
			ans+=abs(x-y);
		} else {
			ans+=1;
			ei[sz++]=minmax(x,y);
		}
	}
	sort(ei,ei+sz,[](const pair<int,int> &a, const pair<int,int> &b) {
			return a.first+a.second<b.first+b.second;
			});
	if (sz) {
		if (k==1) {
			ans+=work(ei,ei+sz,[](pair<int,int> *a, long long b) {});
		} else {
			work(ei,ei+sz,[](pair<int,int> *a,long long b) {
				tmp[a-ei]=b;	
					});
			using R=reverse_iterator<pair<int,int>*>;
			work(R(ei+sz),R(ei),[](R a, long long b) {
				tmp[a.base()-ei]+=b;	
					});
			ans+=*min_element(tmp,tmp+sz);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&k,&n);
  ~~~~~^~~~~~~~~~~~~~
bridge.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d",&a,&x,&b,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	3 ms	448 KB	Output is correct
5	Correct	3 ms	612 KB	Output is correct
6	Correct	2 ms	612 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	2 ms	612 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	2 ms	668 KB	Output is correct
11	Correct	2 ms	684 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	684 KB	Output is correct
2	Correct	2 ms	684 KB	Output is correct
3	Correct	2 ms	740 KB	Output is correct
4	Correct	3 ms	740 KB	Output is correct
5	Correct	3 ms	740 KB	Output is correct
6	Correct	3 ms	740 KB	Output is correct
7	Correct	3 ms	740 KB	Output is correct
8	Correct	3 ms	740 KB	Output is correct
9	Correct	2 ms	740 KB	Output is correct
10	Correct	2 ms	740 KB	Output is correct
11	Correct	2 ms	740 KB	Output is correct
12	Correct	91 ms	10744 KB	Output is correct
13	Correct	183 ms	10872 KB	Output is correct
14	Correct	146 ms	10872 KB	Output is correct
15	Correct	89 ms	10872 KB	Output is correct
16	Correct	98 ms	10872 KB	Output is correct
17	Correct	111 ms	10872 KB	Output is correct
18	Correct	87 ms	10872 KB	Output is correct
19	Correct	122 ms	10872 KB	Output is correct
20	Correct	126 ms	10872 KB	Output is correct
21	Correct	115 ms	10872 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10872 KB	Output is correct
2	Correct	2 ms	10872 KB	Output is correct
3	Correct	2 ms	10872 KB	Output is correct
4	Correct	2 ms	10872 KB	Output is correct
5	Correct	2 ms	10872 KB	Output is correct
6	Correct	2 ms	10872 KB	Output is correct
7	Correct	2 ms	10872 KB	Output is correct
8	Correct	2 ms	10872 KB	Output is correct
9	Correct	2 ms	10872 KB	Output is correct
10	Correct	2 ms	10872 KB	Output is correct
11	Correct	2 ms	10872 KB	Output is correct
12	Correct	2 ms	10872 KB	Output is correct
13	Correct	3 ms	10872 KB	Output is correct
14	Correct	3 ms	10872 KB	Output is correct
15	Correct	3 ms	10872 KB	Output is correct
16	Correct	2 ms	10872 KB	Output is correct
17	Correct	2 ms	10872 KB	Output is correct
18	Correct	2 ms	10872 KB	Output is correct
19	Correct	3 ms	10872 KB	Output is correct
20	Correct	3 ms	10872 KB	Output is correct
21	Correct	3 ms	10872 KB	Output is correct
22	Correct	3 ms	10872 KB	Output is correct
23	Correct	3 ms	10872 KB	Output is correct
24	Correct	3 ms	10872 KB	Output is correct
25	Correct	148 ms	13088 KB	Output is correct
26	Correct	230 ms	14000 KB	Output is correct
27	Correct	335 ms	15600 KB	Output is correct
28	Correct	341 ms	18116 KB	Output is correct
29	Correct	331 ms	20356 KB	Output is correct
30	Correct	136 ms	20356 KB	Output is correct
31	Correct	163 ms	23224 KB	Output is correct
32	Correct	162 ms	25656 KB	Output is correct
33	Correct	130 ms	27468 KB	Output is correct
34	Correct	165 ms	29964 KB	Output is correct
35	Correct	153 ms	31864 KB	Output is correct
36	Correct	169 ms	33920 KB	Output is correct
37	Correct	147 ms	34688 KB	Output is correct

답안 #45535

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 37.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
37.0 / 37.0