Submission #671175

#TimeUsernameProblemLanguageResultExecution timeMemory
671175fatemetmhrPalembang Bridges (APIO15_bridge)C++17
100 / 100
141 ms26312 KiB
// fikhshal chye daram code miznm :} #include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(x) x.begin(), x.end() #define pb push_back #define fi first #define se second const int maxn5 = 3e5 + 10; ll sumrbef[2], cntbef[2], sumlaf[2], cntaf[2], ans[2]; ll pref[maxn5], suf[maxn5]; ll ind[2], per[maxn5], l[maxn5], r[maxn5]; int idl[maxn5], idr[maxn5]; vector <int> st[maxn5], ft[maxn5], pt; inline bool cmp(int i, int j){return l[i] + r[i] < l[j] + r[j];} inline void add_seg(int id){ id = per[id]; st[idl[id]].pb(id); ft[idr[id]].pb(id); for(int t = 0; t < 2; t++) if(ind[t] >= 0 && ind[t] < pt.size()){ ll ver = pt[ind[t]]; if(r[id] < ver){ cntbef[t]++; sumrbef[t] += r[id]; ans[t] += ver - r[id]; } else if(l[id] > ver){ cntaf[t]++; sumlaf[t] += l[id]; ans[t] += l[id] - ver; } } return; } inline void inc(){ ind[1]++; if(ind[1] == pt.size()) return; ll ver = pt[ind[1]]; for(auto id : ft[ind[1] - 1]){ cntbef[1]++; sumrbef[1] += r[id]; } for(auto id : st[ind[1]]){ cntaf[1]--; sumlaf[1] -= l[id]; } ans[1] = cntbef[1] * ver - sumrbef[1] + sumlaf[1] - cntaf[1] * ver; } inline void dec(){ ind[1]--; if(ind[1] < 0) return; ll ver = pt[ind[1]]; for(auto id : ft[ind[1]]){ cntbef[1]--; sumrbef[1] -= r[id]; } for(auto id : st[ind[1] + 1]){ cntaf[1]++; sumlaf[1] += l[id]; } ans[1] = cntbef[1] * ver - sumrbef[1] + sumlaf[1] - cntaf[1] * ver; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> k >> n; ll all = 0; int m = 0; for(int i = 0; i < n; i++){ char c1, c2; cin >> c1 >> l[i] >> c2 >> r[i]; if(l[i] > r[i]) swap(l[i], r[i]); all += r[i] - l[i]; if(c1 != c2){ all++; per[m++] = i; pt.pb(l[i]); pt.pb(r[i]); } } sort(all(pt)); pt.resize(unique(all(pt)) - pt.begin()); for(int i = 0; i < n; i++){ idl[i] = lower_bound(all(pt), l[i]) - pt.begin(); idr[i] = lower_bound(all(pt), r[i]) - pt.begin(); } /* cout << "Points " << endl; for(auto u : pt) cout << u << ' '; cout << endl; */ sort(per, per + m, cmp); // bar hasbe l + r; //for(int i = 0; i < m; i++) // cout << "segment of " << per[i] << ' ' << l[per[i]] << ' ' << r[per[i]] << endl; sumrbef[0] = 0; cntbef[0] = 0; sumlaf[0] = 0; cntaf[0] = 0; sumrbef[1] = 0; cntbef[1] = 0; sumlaf[1] = 0; cntaf[1] = 0; ans[0] = ans[1] = 0; ind[0] = 0; ind[1] = 1; for(int i = 0; i < m; i++){ add_seg(i); while(ind[1] < pt.size() && ans[0] > ans[1]){ ind[0] = ind[1]; sumrbef[0] = sumrbef[1]; cntbef[0] = cntbef[1]; sumlaf[0] = sumlaf[1]; cntaf[0] = cntaf[1]; ans[0] = ans[1]; inc(); } pref[i] = ans[0]; //cout << i << ' ' << ind[0] << ' ' << ind[1] << ' '<< ans[0] << ' ' << ans[1] << endl; } //cout << "all " << all << endl; if(k == 1) return cout << pref[m - 1] * 2 + all << endl, 0; for(int i = 0; i < pt.size(); i++){ st[i].clear(); ft[i].clear(); } sumrbef[0] = 0; cntbef[0] = 0; sumlaf[0] = 0; cntaf[0] = 0; sumrbef[1] = 0; cntbef[1] = 0; sumlaf[1] = 0; cntaf[1] = 0; ans[0] = ans[1] = 0; ind[0] = int(pt.size()) - 1; ind[1] = int(pt.size()) - 2; for(int i = m - 1; i >= 0; i--){ add_seg(i); while(ind[1] >= 0 && ans[0] >= ans[1]){ ind[0] = ind[1]; sumrbef[0] = sumrbef[1]; cntbef[0] = cntbef[1]; sumlaf[0] = sumlaf[1]; cntaf[0] = cntaf[1]; ans[0] = ans[1]; dec(); } suf[i] = ans[0]; //cout << "suff " << i << ' ' << ind[0] << ' ' << ind[1] << ' '<< ans[0] << ' ' << ans[1] << endl; } ll ans = min(pref[m - 1], suf[0]); for(int i = 0; i < m - 1; i++) ans = min(ans, pref[i] + suf[i + 1]); cout << ans * 2 + all << endl; } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

Compilation message (stderr)

bridge.cpp: In function 'void add_seg(int)':
bridge.cpp:28:57: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int t = 0; t < 2; t++) if(ind[t] >= 0 && ind[t] < pt.size()){
      |                                                  ~~~~~~~^~~~~~~~~~~
bridge.cpp: In function 'void inc()':
bridge.cpp:46:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if(ind[1] == pt.size())
      |        ~~~~~~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:123:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         while(ind[1] < pt.size() && ans[0] > ans[1]){
      |               ~~~~~~~^~~~~~~~~~~
bridge.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < pt.size(); i++){
      |                    ~~^~~~~~~~~~~
#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...