oj.uz

Submission #47982

# Submission time Handle Problem Language Result Execution time Memory
47982 2018-05-09T10:06:13 Z yusufake Palembang Bridges (APIO15_bridge) C++
22 / 100
 89 ms 23680 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;

ll A[N],B[N],W[N+N],T[N+N],n,k,nn,t,w,i,x,y,l,m,r,ans;
char c1,c2;

ll f(ll a){
  //  if(!a || a>w) return 1LL<<55;
//	a = W[a];
	ll t=0,i;
	for(i=1;i<=nn;i++)
		t += abs(a - A[i]) + abs(a - B[i]) + 1;
	return t;
}

int main(){
	cin >> k >> n;
	for(i=1;i<=n;i++){
		scanf(" %c%d %c%d",&c1,&x,&c2,&y);
		if(x > y) swap(x,y);
        if(c1 == c2) { ans += y-x; continue; }
		A[++nn] = x; B[nn] = y;
		T[++t] = x; T[++t] = y;
	}
	sort(T+1 , T+t+1); T[0] = -1;
	for(i=1;i<=t;i++) if(T[i] != T[i-1]) W[++w] = T[i];
	
	l=0; r=1LL<<33;
	for(i=44; i--;){
		m = l+r >> 1;
		if(f(m) > f(m+1)) l = m;
		else r = m;
	}
//	cout << l << " ss\n";
	cout << ans + min( f(l-1), min( f(l) , f(l+1) ) );
	return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:22:35: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
   scanf(" %c%d %c%d",&c1,&x,&c2,&y);
                          ~~       ^
bridge.cpp:22:35: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'll* {aka long long int*}' [-Wformat=]
bridge.cpp:33:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   m = l+r >> 1;
       ~^~
bridge.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d",&c1,&x,&c2,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 928 KB Output is correct
8 Correct 2 ms 948 KB Output is correct
9 Correct 3 ms 948 KB Output is correct
10 Correct 3 ms 948 KB Output is correct
11 Correct 3 ms 1028 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1028 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 2 ms 1028 KB Output is correct
4 Correct 2 ms 1028 KB Output is correct
5 Correct 3 ms 1140 KB Output is correct
6 Correct 2 ms 1140 KB Output is correct
7 Correct 3 ms 1140 KB Output is correct
8 Correct 3 ms 1140 KB Output is correct
9 Correct 3 ms 1140 KB Output is correct
10 Correct 2 ms 1140 KB Output is correct
11 Correct 3 ms 1276 KB Output is correct
12 Correct 51 ms 5008 KB Output is correct
13 Correct 89 ms 8864 KB Output is correct
14 Correct 64 ms 8864 KB Output is correct
15 Correct 51 ms 9584 KB Output is correct
16 Correct 56 ms 11540 KB Output is correct
17 Correct 73 ms 15432 KB Output is correct
18 Correct 68 ms 17528 KB Output is correct
19 Correct 84 ms 19716 KB Output is correct
20 Correct 61 ms 20120 KB Output is correct
21 Correct 76 ms 23680 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 23680 KB Output is correct
2 Correct 2 ms 23680 KB Output is correct
3 Incorrect 2 ms 23680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 23680 KB Output is correct
2 Correct 2 ms 23680 KB Output is correct
3 Incorrect 2 ms 23680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 23680 KB Output is correct
2 Correct 2 ms 23680 KB Output is correct
3 Incorrect 2 ms 23680 KB Output isn't correct
4 Halted 0 ms 0 KB -