Submission #1281326

#TimeUsernameProblemLanguageResultExecution timeMemory
1281326Jawad_Akbar_JJPalembang Bridges (APIO15_bridge)C++20
63 / 100
2095 ms8176 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; #define int long long int get(vector<pair<int,int>> vc, int l, int r, int Ans = 0){ for (int i=0;i<vc.size();i++){ if (vc[i].second <= l) Ans += (l - vc[i].second); else if (vc[i].first >= r) Ans += (vc[i].first - r); else if (l <= vc[i].first and r >= vc[i].second) Ans += min(vc[i].first - l,r - vc[i].second); } return Ans * 2; } signed main(){ int k, n, Ans = 0, Sumr = 0, finalAns = 1e17; cin>>k>>n; vector<pair<int,int>> vec; vector<int> pnt; for (int i=1;i<=n;i++){ char a, c; int b, d; cin>>a>>b>>c>>d; if (b > d) swap(b, d); if (a == c) Ans += d - b; else{ vec.push_back({b, d}); pnt.push_back(b); pnt.push_back(d); Ans += d - b + 1; Sumr += b + 1; } } sort(begin(vec), end(vec)); sort(begin(pnt), end(pnt)); pnt.resize(unique(begin(pnt), end(pnt)) - begin(pnt)); finalAns = Ans + Sumr * 2; if (k == 1){ int Rgt = vec.size(), Lft = 0, Suml = 0, id = 0, lst = -1; multiset<int> st; for (int i : pnt){ Sumr -= Rgt * (i - lst); Suml += Lft * (i - lst); while (id < vec.size() and vec[id].first == i) st.insert(vec[id].second), id++, Rgt--; while (st.size() > 0 and *begin(st) == i) Lft++, st.erase(begin(st)); // cout<<i<<" | "<<Lft<<" "<<Suml<<" | "<<Rgt<<" "<<Sumr<<endl; lst = i; finalAns = min(finalAns, Ans + (Suml + Sumr) * 2); } return cout<<finalAns<<endl, 0; } for (int l=0, r=0;l<pnt.size();l++){ int cur = get(vec, pnt[l], pnt[r]); while (r + 1 < pnt.size()){ int Nw = get(vec, pnt[l], pnt[r + 1]); if (Nw <= cur) cur = Nw, r++; else break; } finalAns = min(finalAns, cur + Ans); // cout<<l<<" "<<r<<" "<<cur<<endl; } cout<<finalAns<<'\n'; }
#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...