oj.uz

Submission #1081722

# Submission time Handle Problem Language Result Execution time Memory
1081722 2024-08-30T09:34:40 Z peacebringer1667 Palembang Bridges (APIO15_bridge) C++17
31 / 100
 82 ms 8632 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;

bool type[maxn][2];
int pos[maxn][2];

void input(int n){
	for (int i = 1 ; i <= n ; i++){
		for (int id = 0 ; id <= 1 ; id++){
			char c;int p;
			cin >> c >> p;
			
			type[i][id] = (c == 'A') ? 0 : 1;
			pos[i][id] = p;
		}
	}
}

namespace sub1{
	bool check(int n,int k){
		return (k == 1) && (n <= 1000);
	}
	
	ll calc(int x,int n){
		ll t = 0;
		
		for (int i = 1 ; i <= n ; i++)
		  if (type[i][0] == type[i][1]) t += abs(pos[i][0] - pos[i][1]);
		  else t += abs(pos[i][0] - x) + abs(pos[i][1] - x) + 1;
		return t;
	}
	
	ll solve(int n,int k){
		ll res = LLONG_MAX;
		
		for (int i = 1 ; i <= n ; i++)
		  res = min(res,min(calc(pos[i][0],n),calc(pos[i][1],n)));
		
		return res;
	}
}

namespace sub3{
	bool check(int n,int k){
		return (k == 2 && n <= 100);
	}
	
	ll calc(int x,int y,int n){
		ll t = 0;
		for (int i = 1 ; i <= n ; i++){
			if (type[i][0] == type[i][1]) t += abs(pos[i][0] - pos[i][1]);
			else{
				ll x1 = abs(pos[i][0] - x) + abs(pos[i][1] - x);
				ll x2 = abs(pos[i][0] - y) + abs(pos[i][1] - y); 
				
				t += min(x1,x2) + 1;
			}
		}
		return t;
	}
	
	ll solve(int n,int k){
		vector <int> tmp;
		
		ll res = LLONG_MAX;
		
		for (int i = 1 ; i <= n ; i++){
			tmp.push_back(pos[i][0]);
			tmp.push_back(pos[i][1]);
		}
		sort(tmp.begin(),tmp.end());
		
		for (int x : tmp)
		  for (int y : tmp)
		    if (x <= y) res = min(res,calc(x,y,n));
		return res;
	}
}

namespace sub2{
	bool check(int n,int k){
		return (k == 1);
	}
	
	bool byR(pir x,pir y){
		return (x.se < y.se) || (x.se == y.se && x.fi < y.fi);
	}
	
	vector <pir> L,R;	
    ll simplify(int n){
		int M = n;ll res = 0;
		
		for (int i = 1 ; i <= n ; i++){
			if (type[i][0] == type[i][1])
				res += abs(pos[i][0] - pos[i][1]);
		    else{
		    	if (pos[i][0] > pos[i][1]) swap(pos[i][0],pos[i][1]);
		    	L.push_back({pos[i][0],pos[i][1]});
		    	R.push_back({pos[i][0],pos[i][1]});
			}
		}
		
		
		return res;
	}
	
	ll prelen[maxn],pre[maxn];
	ll suflen[maxn],suf[maxn];
	
	void prepare(){
		sort(L.begin(),L.end(),byR);
		sort(R.begin(),R.end());
		
		for (int i = 0 ; i < L.size() ; i++){
			prelen[i] = ((!i) ? 0 : prelen[i - 1]) + L[i].se - L[i].fi;
			pre[i] = ((!i) ? 0 : pre[i - 1]) + L[i].se + L[i].fi;
		}
		
		for (int i = R.size() - 1; i >= 0; i--){
			suflen[i] = suflen[i + 1] + R[i].se - R[i].fi;
			suf[i] = suf[i + 1] + R[i].fi + R[i].se;
		}
	}
	
	ll calc(int x,ll C){
		ll res = C;
		
		if (x > L[0].se){
			int l = 0,r = L.size() - 1,vt = 0;
			while (l <= r){
				int w = (l + r)/2;
				if (L[w].se < x){
					vt = w;
					l = w + 1;
				}
				else r = w - 1;
			}
			
			res -= prelen[vt];
			res += 2*(ll)x*(ll)(vt + 1) - pre[vt];
		}
		
		if (x < R.back().fi){
			int l = 0,r = R.size() - 1,vt = R.size() - 1;
			
			while (l <= r){
				int w = (l + r)/2;
				if (R[w].fi > x){
					vt = w;
					r = w - 1;
				}
				else l = w + 1;
			}
			
			res -= suflen[vt];
			res += suf[vt] - 2*(ll)x*(ll)(R.size() - vt);
		}
		
		res += L.size();
		
		return res;
	}
	
	ll solve(int n,int k){
		ll res = simplify(n);
		
		if (!L.size()) return res;
		
		prepare();
		
		ll T = LLONG_MAX,C = 0;
		
		for (pir t : L)
		  C += t.se - t.fi;
		
		for (int i = 1 ; i <= n ; i++)
		  T = min(T,min(calc(pos[i][0],C),calc(pos[i][1],C)));
		
		return res + T;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	freopen("B.inp","r",stdin);
//	freopen("B.out","w",stdout);
	int k,n;
	cin >> k >> n;
	input(n);
	
	if (sub1::check(n,k))
	  cout << sub1::solve(n,k) << "\n";else
	
	if (sub2::check(n,k))
	  cout << sub2::solve(n,k) << "\n";else
	  ;
	if (sub3::check(n,k))
	  cout << sub3::solve(n,k);else


	return 0;
}

Compilation message

bridge.cpp: In function 'long long int sub2::simplify(int)':
bridge.cpp:99:7: warning: unused variable 'M' [-Wunused-variable]
   99 |   int M = n;ll res = 0;
      |       ^
bridge.cpp: In function 'void sub2::prepare()':
bridge.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i = 0 ; i < L.size() ; i++){
      |                    ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 472 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 488 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 27 ms 7120 KB Output is correct
13 Correct 82 ms 8624 KB Output is correct
14 Correct 76 ms 7104 KB Output is correct
15 Correct 48 ms 6084 KB Output is correct
16 Correct 24 ms 7872 KB Output is correct
17 Correct 53 ms 8628 KB Output is correct
18 Correct 34 ms 8132 KB Output is correct
19 Correct 77 ms 8632 KB Output is correct
20 Correct 35 ms 8124 KB Output is correct
21 Correct 53 ms 8328 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 9 ms 476 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 10 ms 488 KB Output is correct
12 Correct 6 ms 348 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 8 ms 480 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 9 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 6 ms 484 KB Output is correct
11 Correct 7 ms 476 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Incorrect 1 ms 472 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 11 ms 480 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 8 ms 348 KB Output is correct
8 Correct 7 ms 480 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 7 ms 348 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -