Submission #922588

#TimeUsernameProblemLanguageResultExecution timeMemory
922588NonozePalembang Bridges (APIO15_bridge)C++17
100 / 100
716 ms221408 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set; typedef long long ll; #define int long long #define sz(x) (int)(x.size()) #define debug(x) cerr << (#x) << ": " << (x) << endl #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() struct node { int left, right; int sum, nb; node() {left=-1, right=-1, sum=0, nb=0;} }; vector<vector<node>> st(2); void create(int empl) { st[empl].push_back(node()); } void updatte(int empl, int node) { int nb=0, sum=0; if (st[empl][node].left!=-1) nb+=st[empl][ st[empl][node].left ].nb, sum+=st[empl][ st[empl][node].left ].sum; if (st[empl][node].right!=-1) nb+=st[empl][ st[empl][node].right ].nb, sum+=st[empl][ st[empl][node].right ].sum; st[empl][node].nb=nb, st[empl][node].sum=sum; } void update(int empl, int node, int left, int right, int qval, int value) { if (left==right) { st[empl][node].nb+=value; st[empl][node].sum+=value*left; return; } int mid=(left+right)/2; if (mid>=qval) { if (st[empl][node].left==-1) { create(empl); st[empl][node].left=sz(st[empl])-1; } update(empl, st[empl][node].left, left, mid, qval, value); } else { if (st[empl][node].right==-1) { create(empl); st[empl][node].right=sz(st[empl])-1; } update(empl, st[empl][node].right, mid+1, right, qval, value); } updatte(empl, node); } int milieu; int query(int empl, int node, int left, int right, int qval) { if (left==right) { milieu=left; return 0; } int mid=(left+right)/2; int ans=0; if (st[empl][node].left!=-1 && st[empl][ st[empl][node].left ].nb>=qval) { ans=query(empl, st[empl][node].left, left, mid, qval); if (st[empl][node].right!=-1) { ans+=st[empl][ st[empl][node].right ].sum-st[empl][ st[empl][node].right ].nb*milieu; } } else if (st[empl][node].right!=-1) { int moins=0; if (st[empl][node].left!=-1) moins=st[empl][ st[empl][node].left].nb; ans=query(empl, st[empl][node].right, mid+1, right, qval-moins); if (st[empl][node].left!=-1) { ans+=st[empl][ st[empl][node].left ].nb*milieu-st[empl][ st[empl][node].left ].sum; } } return ans; } struct traj { int l, r; double mid; }; vector<traj> a; int n, k, m; void solve() { cin >> k >> n; int res=0; for (int i=0; i<n; i++) { char aa, bb; int aaa, bbb; cin >> aa >> aaa >> bb >> bbb; if (aa==bb) { res+=abs(aaa-bbb); continue; } if (aaa>bbb) swap(aaa, bbb); a.push_back(traj{aaa, bbb, (double)(aaa+bbb)/2.0}); } n=sz(a); res+=n; if (n==0) { cout << res << endl; return; } sort(all(a), [](traj &A, traj &B){return A.mid<B.mid;}); create(0), create(1); for (int i=0; i<n; i++) { update(0, 0, 0, (int)1e9, a[i].l, 1); update(0, 0, 0, (int)1e9, a[i].r, 1); } if (k==1) { cout << res+query(0, 0, 0, (int)1e9, n) << endl; return; } int ans=LLONG_MAX; for (int i=0; i<n; i++) { int s1=query(0, 0, 0, (int)1e9, (n-i)); int s2=query(1, 0, 0, (int)1e9, i); ans=min(ans, s1+s2); update(0, 0, 0, (int)1e9, a[i].l, -1); update(0, 0, 0, (int)1e9, a[i].r, -1); update(1, 0, 0, (int)1e9, a[i].l, 1); update(1, 0, 0, (int)1e9, a[i].r, 1); } cout << res+ans << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt=1;// cin >> tt; while(tt--) 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...