Submission #407093

#TimeUsernameProblemLanguageResultExecution timeMemory
407093tranxuanbachPalembang Bridges (APIO15_bridge)C++17
22 / 100
53 ms6124 KiB
#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; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (int i = l; i < r; i++) #define ForE(i, l, r) for (int i = l; i <= r; i++) #define FordE(i, l, r) for (int i = l; i >= r; i--) #define Fora(v, a) for (auto v: a) #define bend(a) a.begin(), a.end() #define isz(a) ((signed)a.size()) typedef long long ll; typedef long double ld; typedef pair <int, int> pii; typedef vector <int> vi; typedef vector <pii> vpii; typedef vector <vi> vvi; const int N = 1e5 + 5; struct Citizen{ char P; int S; char Q; int T; Citizen(char P = '?', int S = 0, char Q = '?', int T = 0): P(P), S(S), Q(Q), T(T){ } }; int k, n; Citizen citizens[N]; ll ans; pii a[N]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("KEK.inp", "r", stdin); // freopen("KEK.out", "w", stdout); cin >> k >> n; ForE(i, 1, n){ cin >> citizens[i].P >> citizens[i].S >> citizens[i].Q >> citizens[i].T; } { int tn = 0; ForE(i, 1, n){ if (citizens[i].P == citizens[i].Q){ ans += abs(citizens[i].S - citizens[i].T); continue; } a[++tn] = make_pair(min(citizens[i].S, citizens[i].T), max(citizens[i].S, citizens[i].T)); ans += a[tn].se - a[tn].fi + 1; } n = tn; } if (k == 1){ vi cac; ForE(i, 1, n){ cac.emplace_back(a[i].fi); cac.emplace_back(a[i].se); } sort(bend(cac)); int pos = cac[n]; ForE(i, 1, n){ ans += 2 * max(0, max(a[i].fi - pos, pos - a[i].se)); } cout << ans << endl; } } /* is this slope trick? ==================================================+ INPUT: | --------------------------------------------------| 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#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...