Submission #1228539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228539		Bui_Quoc_Cuong	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	95 ms	10792 KiB

bridge

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) A.begin(), A.end()
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)b; i--)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define se second
const int oo = (int) 2e9;
const long long INF = (long long) 1e18;
const int MAXN = (int) 4e5 + 5;

int K, N;
char P[MAXN], Q[MAXN];
int S[MAXN], T[MAXN];

namespace sub1 {
	int A[MAXN];
	int M;
	long long res = 0;
	long long pre[MAXN];

	void solve() {
		FOR(i, 1, N) {
			if (P[i] != Q[i]) {
				A[++ M] = S[i];
				A[++ M] = T[i];
			} else res+= abs(S[i] - T[i]);
		}

		N = M;
		sort(A + 1, A + 1 + N);
		FOR(i, 1, N) pre[i] = pre[i - 1] + A[i];

		long long ans = (N > 0 ? INF : 0);

		FOR(i, 1, N) {
			int x = A[i];
			long long sum = 1LL * i * x - pre[i] - 1LL * (N - i + 1) * x + pre[N] - pre[i - 1];
			ans = min(ans, sum);
		}

		cout << res + ans + N / 2;
	}		
}

namespace sub2 {
	int A[MAXN];
	int M;
	long long res = 0;

	void solve() {
		vector <int> Place;
		FOR(i, 1, N) {
			if (P[i] == Q[i]) res+= abs(S[i] - T[i]);
			else {
				Place.push_back(S[i]);
				Place.push_back(T[i]);
			}
		}

		sort(ALL(Place));

		long long ans = (Place.size() > 1 ? INF : 0);	

		FOR(i, 0, Place.size() - 1) {
			int x1 = Place[i];
			FOR(j, i + 1, Place.size() - 1) {
				int x2 = Place[j];
				long long sum = 0;

				FOR(t, 1, N) if (P[t] != Q[t]) {
					sum+= min(abs(S[t] - x1) + abs(T[t] - x1), abs(S[t] - x2) + abs(T[t] - x2)) + 1;
				}

				ans = min(ans, sum);	
			}
		}
		cout << ans + res;
	}		
}

namespace sub3 {
	vector <pair <int, int>> Line;
	long long res = 0;
	long long L[MAXN], R[MAXN];

	void solve() {
		FOR(i, 1, N) {
			if (P[i] != Q[i]) {
				if (S[i] > T[i]) swap(S[i], T[i]);
				Line.push_back(make_pair(S[i], T[i]));
			} else res+= abs(S[i] - T[i]);
		}					

		sort(ALL(Line), [&](pair <int, int> u, pair <int, int> v) {
			return u.fi + u.se < v.fi + v.se;
		});

		N = Line.size() - 1;	

		/// calc For Left
		vector <int> Point;

		FOR(i, 0, N) {
			Point.push_back(Line[i].fi);
			Point.push_back(Line[i].se);

			sort(ALL(Point));	

			int x = Point[(Point.size() + 1) / 2];

			long long sum = 0;

			for (const int &xxx : Point) sum+= abs(xxx - x);

			L[i] = sum;
		}	

		Point.clear();
		/// calc For Right

		FORD(i, N, 0) {
			Point.push_back(Line[i].fi);
			Point.push_back(Line[i].se);

			sort(ALL(Point));	

			int x = Point[(Point.size() + 1) / 2];

			long long sum = 0;

			for (const int &xxx : Point) sum+= abs(xxx - x);

			R[i] = sum;
		}

		long long ans = (N > 0 ? INF : 0);

		FOR(i, 0, N - 1) {
			ans = min(ans, L[i] + R[i + 1]);
		}

		cout << ans + res + N + 1;
	}
}

namespace sub4 {
	int deCompress[MAXN];
	vector <pair <int, int>> Line;
	long long res = 0;
	int VAL;
	long long L[MAXN], R[MAXN];	

	void Compress(void) {
		vector <int> X;
		FOR(i, 0, N) {
			X.push_back(Line[i].fi);
			X.push_back(Line[i].se);
		}
		sort(ALL(X)); X.resize(unique(ALL(X)) - X.begin());	

		FOR(i, 0, N) {
			int p_X = upper_bound(ALL(X), Line[i].fi) - X.begin();
			deCompress[p_X] = Line[i].fi, Line[i].fi = p_X;

			int p_Y = upper_bound(ALL(X), Line[i].se) - X.begin();
			deCompress[p_Y] = Line[i].se, Line[i].se = p_Y;
		}

		VAL = X.size();
	}

	struct FenwickTree {
		long long bit[MAXN];

		inline void update(int u, int val) {
			for (int i = u; i <= VAL; i+=i&-i) bit[i]+= val;
		}

		inline long long get(int u) {
			long long sum = 0;
			for (int i = u; i; i-=i&-i) sum+= bit[i];
			return sum;
		}

		inline long long get(int l, int r) {
			return get(r) - get(l - 1);
		}

		void clear() {
			memset(bit, 0, sizeof bit);
		}
	} fwtSum, fwtCnt;

	void calcLeft(void) {
		fwtSum.clear();
		fwtCnt.clear();

		FOR(i, 0, N - 1) {
			fwtCnt.update(Line[i].fi, 1); fwtCnt.update(Line[i].se, 1);
			fwtSum.update(Line[i].fi, deCompress[Line[i].fi]); fwtSum.update(Line[i].se, deCompress[Line[i].se]);

			int median = 0, l = 1, r = VAL;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (fwtCnt.get(mid) > i) median = mid, r = mid - 1;
				else l = mid + 1;
			}	

			long long sumLeft = 1LL * deCompress[median] * fwtCnt.get(median) - fwtSum.get(median);
			long long sumRight = fwtSum.get(median, VAL) - 1LL * deCompress[median] * fwtCnt.get(median, VAL);

			L[i] = sumLeft + sumRight;
		}
	}	

	void calcRight(void) {
		fwtSum.clear();
		fwtCnt.clear();
		int cnt = 0;

		FORD(i, N, 0) {
			cnt++;
			fwtCnt.update(Line[i].fi, 1); fwtCnt.update(Line[i].se, 1);
			fwtSum.update(Line[i].fi, deCompress[Line[i].fi]); fwtSum.update(Line[i].se, deCompress[Line[i].se]);

			int median = 0, l = 1, r = VAL;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (fwtCnt.get(mid) >= cnt) median = mid, r = mid - 1;
				else l = mid + 1;
			}	

			long long sumLeft = 1LL * deCompress[median] * fwtCnt.get(median) - fwtSum.get(median);
			long long sumRight = fwtSum.get(median, VAL) - 1LL * deCompress[median] * fwtCnt.get(median, VAL);

			R[i] = sumLeft + sumRight;
		}
	}

	void solve() {	
		FOR(i, 1, N) {
			if (P[i] != Q[i]) {
				if (S[i] > T[i]) swap(S[i], T[i]);
				Line.push_back(make_pair(S[i], T[i]));
			} else res+= abs(S[i] - T[i]);
		}					

		sort(ALL(Line), [&](pair <int, int> u, pair <int, int> v) {
			return u.fi + u.se < v.fi + v.se;
		});

		N = Line.size() - 1;

		Compress();
		calcLeft(); calcRight();

		long long ans = (N > 0 ? INF : 0);
		FOR(i, 0, N - 1) ans = min(ans, L[i] + R[i + 1]);

		cout << ans + res + N + 1;
	}
}

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    #define Hori "" 
    if (fopen(Hori".inp", "r")) {
        freopen(Hori".inp", "r", stdin);
        freopen(Hori".out", "w", stdout);
    }
    
    cin >> K >> N;
    for (int i = 1; i <= N; i++) cin >> P[i] >> S[i] >> Q[i] >> T[i];

    if (K == 1) return sub1 :: solve(), 0;
	return sub4 :: solve(), 0;

    return void(cerr << "KO :" << TIME << "s "), (0 ^ 0);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:273:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         freopen(Hori".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:274:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         freopen(Hori".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37