oj.uz

답안 #679188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679188 2023-01-07T16:35:13 Z penguin133 Palembang Bridges (APIO15_bridge) C++17
0 / 100
 1 ms 340 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<pi> st, en;
bool vis[100005], vis2[100005];
int P[100005], S[100005];
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({b, i}), en.push_back({d, i}), tmp += abs(b - d) + 1;
	}
	if(k == 2){
		cout << ans + tmp << '\n';
		return;
	}
	sort(st.begin(), st.end());
	sort(en.begin(), en.end());
	int mn = 1e18;
	int in = 0, cur = 0, heh = 0;
	int lol = 0;
	for(auto [i, j] : st){
		while(in < (int)en.size() && en[in].fi <= i){
			vis2[en[in].se] = 1;
			if(vis[en[in].se] == 1 && vis2[en[in].se] == 1)cur += en[in].fi, heh++;
			in++;
		}	
		vis[j] = 1;
		if(vis[j] == 1 && vis2[j] == 1)heh++, cur += i;
		P[++lol] = 2 * (heh * i - cur);
	}
	in = (int)en.size() - 1, cur = 0, heh = 0;
	for(int i=1;i<=n;i++)vis[i] = vis2[i] = 0;
	for(int a=(int)st.size()-1;a>=0;a--){
		int i = st[a].fi, j = st[a].se;
		while(in >= 0 && en[in].fi >= i){
			vis2[en[in].se] = 1;
			if(vis[en[in].se] == 1 && vis2[en[in].se] == 1)cur += en[in].fi, heh++;
			in--;
		}
		vis[j] = 1;
		if(vis[j] == 1 && vis2[j] == 1)heh++, cur += i;
		S[a + 1] = 2 * (cur - heh * i);
	}
	for(int i=1;i<=(int)st.size();i++)mn = min(mn, P[i] + S[i]);// cout << P[i] << " " << S[i] << '\n';
	//cout << ans << " " << tmp << " " << mn << '\n';
	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:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

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