제출 #485425

#제출 시각아이디문제언어결과실행 시간메모리
485425BackNoobPalembang Bridges (APIO15_bridge)C++14
0 / 100
2 ms460 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 3e5 + 227; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } struct item{ int b1 , z1 , b2 , z2; } a[mxN]; vector<int> co; struct fenwicktree{ vector<pair<ll , ll>> bit; int n; fenwicktree(){} fenwicktree(int _n) { n = _n; bit.resize(n + 7 , {0 , 0}); } void update(int pos , int val) { int x = co[pos - 1]; if(val < 0) x = -x; for(; pos <= n ; pos += (pos & (-pos))) { bit[pos].fi += val; bit[pos].se += x; } } int sum(int pos) { int res = 0; for(; pos > 0 ; pos -= (pos & (-pos))) res += bit[pos].fi; return res; } int sumval(int pos) { ll res = 0; for(; pos > 0 ; pos -= (pos & (-pos))) res += bit[pos].se; return res; } ll median() { int lo = 0 , hi = n; int le = sum(n); while(lo + 1 < hi) { int mid = (lo + hi) / 2; if(sum(mid) >= (le + 1) / 2) hi = mid; else lo = mid; } ll ans = 0; ans += 1LL * co[hi - 1] * sum(hi) - sumval(hi); ans += sumval(n) - sumval(hi) - 1LL * (sum(n) - sum(hi)) * co[hi - 1]; return ans; } } ft1 , ft2; int n , k; pair<int , int> val[mxN]; int cnt[mxN]; int compress(int x) { return lower_bound(all(co) , x) - co.begin() + 1; } ll res1 = infll , res2 = infll; ll ans1[mxN] , ans2[mxN]; void modify(int x , int y) { ft1.update(x , 1); ft1.update(y , 1); ft2.update(x , -1); ft2.update(y , -1); res1 = ft1.median(); res2 = ft2.median(); } int CNT[mxN]; void solve() { cin >> k >> n; for(int i = 1 ; i <= n ; i++) { char c1 , c2; cin >> c1 >> a[i].b1 >> c2 >> a[i].b2; a[i].z1 = (c1 == 'A' ? 1 : 2); a[i].z2 = (c2 == 'A' ? 1 : 2); } for(int i = 1 ; i <= n ; i++) { if(a[i].z1 == a[i].z2) continue; co.pb(a[i].b1); co.pb(a[i].b2); } sort(all(co)); co.erase(unique(all(co)) , co.end()); for(int i = 1 ; i <= n ; i++) { a[i].b1 = compress(a[i].b1); a[i].b2 = compress(a[i].b2); } ll re = 0; int cnt = 0; for(int i = 1 ; i <= n ; i++) { if(a[i].z1 == a[i].z2) { re += abs(a[i].b1 - a[i].b2); continue; } val[++cnt] = {a[i].b1 , i}; val[++cnt] = {a[i].b2 , i}; } sort(val + 1 , val + 1 + cnt); ft1 = fenwicktree(cnt); ft2 = fenwicktree(cnt); for(int i = 1 ; i <= n ; i++) { if(a[i].z1 == a[i].z2) continue; ft2.update(a[i].b1 , 1); ft2.update(a[i].b2 , 1); } res1 = ft1.median(); res2 = ft2.median(); sort(val + 1 , val + 1 + cnt); if(k == 1) { cout << res2 + re + cnt / 2; } // for(int i = 1 ; i <= cnt ; i++) { // pair<int , int> it = val[i]; // CNT[it.se]++; // if(CNT[it.se] == 2) { // modify(a[it.se].b1 , a[it.se].b2); // } // ans1[i] = res1; // ans2[i] = res2; // } // if(k == 2) { // ll ans = infll; // for(int i = 1 ; i <= cnt ; i++) { // if(minimize(ans , ans1[i] + ans2[i]) == true) { // } // } // cout << ans + re + cnt / 2 << endl; // } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); //freopen(TASK".inp" , "r" , stdin); //freopen(TASK".out" , "w" , stdout); int tc = 1; //cin >> tc; while(tc--) { solve(); } 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...