oj.uz

답안 #679190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679190 2023-01-07T16:43:27 Z penguin133 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 97 ms 5892 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
 
int n, k;
vector<int> st, en;
bool vis[100005], vis2[100005];
int P[100005], S[100005];
vector<int> pos;
void solve(){
	cin >> k >> n;
	int ans = 0, tmp = 0;
	for(int i=1;i<=n;i++){
		char a, c; int b, d; cin >> a >> b >> c >> d;
		if(a == c)ans += abs(b - d);
		else st.push_back(max(b, d)), en.push_back(min(b, d)), tmp += abs(b - d) + 1, pos.push_back(b), pos.push_back(d);
	}
	if(k == 2){
		cout << ans + tmp << '\n';
		return;
	}
	sort(st.begin(), st.end());
	sort(en.begin(), en.end());
	if(st.size())P[0] = st[0];
	int mn = (st.size() ? 1e18 : 0);
	for(int i=1;i<(int)st.size();i++)P[i] = P[i-1] + st[i];
	for(int i=(int)en.size()-1;i>=0;i--)S[i] = S[i+1] + en[i];
	for(auto i : pos){
		int cur = 0;
		int x = upper_bound(st.begin(), st.end(), i) - st.begin();
		if(x != 0){
			x--;
			cur += 2 * ((x + 1) * i - P[x]);
		}
		x = upper_bound(en.begin(), en.end(), i) - en.begin();
		if(x != (int)en.size()){
			cur += 2 * (S[x] - i * ((int)en.size() - x));
		}
		//cout << i << " " << cur << '\n';
		mn = min(mn, cur);
	}
	cout << ans + tmp + mn;
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

bridge.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 380 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 28 ms 5724 KB Output is correct
13 Correct 94 ms 5892 KB Output is correct
14 Correct 79 ms 5328 KB Output is correct
15 Correct 58 ms 3884 KB Output is correct
16 Correct 36 ms 5764 KB Output is correct
17 Correct 44 ms 5720 KB Output is correct
18 Correct 45 ms 5824 KB Output is correct
19 Correct 97 ms 5768 KB Output is correct
20 Correct 38 ms 5836 KB Output is correct
21 Correct 57 ms 5752 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -