Submission #1086186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086186		Hadi_Alhamed	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	69 ms	8140 KiB

bridge

// to live is to die
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n)              \
  for (int i = 0; i <= n; i++) { \
    a[i] = 0;                    \
  }
#define clearMat(a, n, m, d)                  \
  for (int i = 0; i <= n; i++) {              \
    for (int j = 0; j <= m; j++) a[i][j] = d; \
  }
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)

#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define db(x...)                \
  cerr << "[" << #x << "] = ["; \
  _print(x)
#else
#define db(x...)
#endif

// order_of_key(k): # of elements less than k (which is the index of x = k)
// find_by_order(k); iterator of the k-th element

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,
                              tree_order_statistics_node_update>;
template <class T>
bool ckmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &a) {
  for (auto &x : a) in >> x;
  return in;
};
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
  for (auto &x : a) out << x << ' ';
  return out;
};

// priority_queue<data type , the container that would hold the values ,
// greater<pair<int,int>>> greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m

ll const MAX = 1e18 + 1;
ll const oo = 3e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
ll const SIZE = 2e5 + 900;
const int LOG = 20;

template <typename T, typename T2>
T add(T X, T2 Y) {
  X += Y;
  if (X >= MOD) {
    X -= MOD;
  }
  return X;
}
template <typename T, typename T2>

T sub(T X, T2 Y) {
  X -= Y;
  if (X < 0) X += MOD;
  return X;
}

template <typename T, typename T2>
T mult(T X, T2 Y) {
  return (X % MOD) * (Y % MOD) % MOD;
}

void setIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

// bool operator <s (const type & obj1 , const type & obj2){....}




void solve()
{
	
	int K , N;
	cin >> K >> N;
	ll same = 0 , sumL{} , sumR{};
	priority_queue<ll>L;
	priority_queue<ll , vector<ll> , greater<ll>>R;
	vpl V = {{0 , 0}};
	rep(i , N)
	{
		char a , b ;
		ll s , t;
		cin >> a >> s >> b >> t;
		if(a == b)
		{
			same += abs(s - t);
		}else{
			V.PB({s , t});
		}
	}	
	//find median of All Ts and Ss
	auto handle_insert = [&](ll X)->void
	{
		ll mid = L.empty() ? oo : L.top();
		if(X <= mid)
		{
			L.push(X);
			sumL += X;
		}else{
			R.push(X);
			sumR += X;
		}
		if(R.size() + 1 < L.size())
		{
			ll x = L.top();
			L.pop();
			R.push(x);
			sumR += x;
			sumL -= x;
		}else if(L.size() < R.size())
		{
			ll x = R.top();
			R.pop();
			L.push(x);
			sumR -= x;
			sumL += x;
		}
	};
	sort(all(V) , [&](pl p1 , pl p2)->bool
	{
		return p1.F + p1.S < p2.F + p2.S;
	});
	ll add = same + (ll)V.size() - 1;
	vl pref(N + 10);
	int _N = (int)V.size() - 1;
	for(int i = 1; i <= _N ; i ++)
	{
		handle_insert(V[i].F);
		handle_insert(V[i].S);
		pref[i] = sumR - sumL;
	}
	ll answer = pref[_N];
	if(K == 2)
	{
		while(R.size())R.pop();
		while(L.size())L.pop();
		sumL = 0 ; sumR = 0;
		for(int i = _N ; i >= 1 ; i--)
		{
			handle_insert(V[i].F);
			handle_insert(V[i].S);
			answer = min(answer , sumR - sumL + pref[i - 1]);
		}
	}
	cout << answer + add << "\n";	
		
		
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	// setIO("hayfeast");
	// cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:154:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:155:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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