Submission #1070393

#TimeUsernameProblemLanguageResultExecution timeMemory
1070393MuhammetPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define sz(x) (int)x.size() #define ff first #define ss second const int N = 300005; const int M = 1e9 + 7; int T, n, k, s1[N], s2[N]; char c1[N], c2[N]; vector <int> p, f, df, ds, ndf, nds; int f1(int x){ int p1 = (lower_bound(ds.begin(), ds.end(), x) - ds.begin() - 1), f1 = (upper_bound(df.begin(), df.end(), x) - df.begin()); int y = 0; if(p1 >= 0) y += p[p1] + (abs(x-ds[p1]) * (nds[p1])); if(f1 < sz(f)) y += f[f1] + (abs(x-df[f1]) * (ndf[f1])); return y*2; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> k >> n; for(int i = 1; i <= n; i++){ cin >> c1[i] >> s1[i] >> c2[i] >> s2[i]; } int ans1 = 0; vector <pair <int,int>> v; for(int i = 1; i <= n; i++){ ans1 += abs(s1[i]-s2[i]); if(c1[i] != c2[i]) { ans1++; v.push_back({min(s1[i],s2[i]),max(s1[i],s2[i])}); } } sort(v.begin(), v.end()); p.assign(sz(v),0); f.assign(sz(v),0); for(int i = 0; i < sz(v); i++){ df.push_back(v[i].ff); ds.push_back(v[i].ss); } sort(ds.begin(), ds.end()); sort(df.begin(), df.end()); int x = 0; ndf.assign(sz(v),0); nds.assign(sz(v),0); for(int i = 1; i < sz(v); i++){ x += (ds[i]-ds[i-1]) * (i+1); p[i] = x; nds[i] = i+1; } x = 0; int cnt = 0; for(int i = sz(v)-2; i >= 0; i--){ cnt++; x += (df[i+1]-df[i]) * cnt; f[i] = x; ndf[i] = cnt; } int mn = 1e18; for(int i = 0; i < sz(v); i++){ mn = min(f1(df[i]),mn); mn = min(f1(ds[i]),mn); } cout << mn + ans1 << "\n"; return 0; }
#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...