Submission #720274

#TimeUsernameProblemLanguageResultExecution timeMemory
720274BoomydayPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms300 KiB
// // Created by adavy on 2/12/2023. // #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; using ll = long long; using ld = long double; using db = double; using str = string; // yay python! using ii = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>; using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>; using vd = vector<db>; using vs = vector<str>; using vii = vector<ii>; using vpl = vector<pl>; using vpd = vector<pd>; using ost = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>; // pairs #define mp make_pair #define f first #define s second #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define trav(a,x) for (auto& a: x) #define all(x) begin(x), end(x) #define pb push_back const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; const ll INF = 1e18; // not too close to LLONG_MAX const ld PI = acos((ld)-1); // TOP > BOTTOM multiset<ll, greater<ll>> top1, top2; multiset<ll> bottom1, bottom2; ll ts1, bs1, ts2, bs2; void chk(multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){ if ((int)top.size()-1 > (int)bottom.size()) { ll temp = *top.begin(); top.erase(top.find(temp)); bottom.insert(temp); ts-=temp; bs+=temp; } if ((int)bottom.size() > (int)top.size()) { ll temp = *bottom.begin(); bottom.erase(bottom.find(temp)); top.insert(temp); bs-=temp; ts+=temp; } } void ins(ll x, multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){ if (top.size()==0) {top.insert(x); ts+=x;} else if (x>*top.begin()) {bottom.insert(x); bs+=x;} else {top.insert(x); ts+=x;}; chk(top, bottom, ts, bs); } void re(ll x, multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){ if (top.find(x) != top.end()) {top.erase(top.find(x)); ts-=x;} else {bottom.erase(bottom.find(x)); bs-=x;} chk(top, bottom, ts, bs); } ll calc(multiset<ll, greater<ll>> top, multiset<ll> bottom, ll ts, ll bs){ ll m = *top.begin(); return m*(top.size()) - ts - m*(bottom.size()) + bs; } int main(){ int n, k; cin >> k >> n; ll leftover = 0; vl nums; F0R(_, n){ char l1, l2; ll n1, n2; cin >> l1 >> n1 >> l2 >> n2; if(l1==l2) leftover += abs(n2-n1); else { nums.pb(n1); nums.pb(n2); } } sort(all(nums)); if(k==1){ ll md = nums[nums.size()/2]; ll ans = 0; trav(i, nums){ ans += abs(md-i); } cout << ans+leftover << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...