제출 #233632

#제출 시각아이디문제언어결과실행 시간메모리
233632balbitPalembang Bridges (APIO15_bridge)C++14
100 / 100
1484 ms124388 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define ll long long using namespace std; #ifdef BALBIT #define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__) template<typename T> void _do(T && x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);} #define IOS() #else #define bug(...) #define IOS() ios::sync_with_stdio(0), cin.tie(0) #define endl '\n' #endif // BALBIT //#define int ll #define pii pair<ll, ll> #define f first #define s second #define ALL(x) x.begin(), x.end() #define SZ(x) (int)(x.size()) #define pb push_back vector<pii> v; int n; const int maxn = 1e5+3; vector<int> rbs, lbs;// right bounds and left bounds, separated and sorted ll rps[maxn], lps[maxn];// right bounds and left bounds, separated and sorted and ps struct node{ int l=0,r=0; ll val=0; int sz=0; } tree [maxn<<6]; int T_cnt = 0; //inline ll getval(node *&o){return o?o->val:0;} //inline int getsz(node *&o){return o?o->sz:0;} // void build(int &o, int l, int r) { o = T_cnt++; if (l == r) { return; } int mid = (l+r)/2; build(tree[o].l,l,mid); build(tree[o].r,mid+1,r); } inline void MO(int &i,int l,int r, ll num, ll v) //&的神奇功能,会把外面传入变量一起改变 { tree[T_cnt++]=tree[i]; //先继承上一棵树的信息 i=T_cnt-1; //修改子树关系 ++tree[i].sz; tree[i].val += v; if (l==r) return; int mid=(l+r)>>1; if (num<=mid) MO(tree[i].l,l,mid,num,v); //小于等于mid则在左边更新,右边直接与上一棵树共用 else MO(tree[i].r,mid+1,r,num,v); //大于mid,左边更新,右边共用 // tree[i].sz = tree[i].l.sz + tree[i].r.sz; // tree[i].val = tree[i].l.val + tree[i].r.val; } ll A=0, B=0; void QU(int o, int l, int r, int L, int R) { if (l > R || r<L) return; if (l>=L && r <=R) { A += tree[o].val; B += tree[o].sz; return; // tree[o].val, tree[o].sz; } ll mid = (l+r)/2; QU(tree[o].l, l,mid, L, R); QU(tree[o].r,mid+1,r, L, R); // return {A.f+B.f, A.s+B.s}; } vector<int> lhistory, rhistory; vector<int> lrev; map<ll, int> segmp; ll C(ll l, ll r) { // return matrix[l][r]; // if (l>r) return 10000000000000000ll; int L = lower_bound(ALL(rbs), l) - rbs.begin() -1;// right bounds less than l int R = upper_bound(ALL(lbs), r) - lbs.begin();// right bounds less than l ll re = 0; re += (lps[n] - lps[R]) - (n-R) * r; // bug(re); // bug(L+1); re += (L+1) * (l) - (rps[L+1]); // bug(re); int lat = lower_bound(ALL(lrev), l, greater<int>()) - lrev.begin() - 1; int rat = lower_bound(ALL(rbs), r) - rbs.begin()-1; // bug(lat, rat); auto sit = segmp.lower_bound(r+l); A=B=0; QU(lhistory[lat+1], 0, 1e5+3, 0, (*prev(sit)).s); re += A - B * l; A=B=0; QU(rhistory[rat+1], 0, 1e5+3, (*(sit)).s, 1e5+3); re += B*r-A; return re; } ll RE; vector<int> p; int m; // node * lroot = 0, *rroot = 0; vector<int> smawk(vector<int> row, vector<int> col){ bug("SMAWK!", SZ(row), SZ(col)); #ifdef BALBIT cout<<"R: "; for (int x : row) cout<<x<<' '; cout<<endl; cout<<"C: "; for (int x : col) cout<<x<<' '; cout<<endl; #endif if (SZ(col) <= 4) { vector<int> ret; for (int i = 0; i<SZ(row); ++i){ ll mybest = 1e18+2; ret.pb(0); for (int j = 0; j<SZ(col); ++j) { ll cc = C(row[i], col[j]); if (cc < mybest) { ret.back() = col[j]; mybest = cc; } } RE=min(RE,mybest); } return ret; } if (SZ(col) > SZ(row)) { // Reduce! vector<int> nc; // Stack of surviving columns for (ll cc : col) { while (true) { if (nc.size() == 0) break; ll rr = row[nc.size() - 1]; if (C(rr, cc) > C(rr, nc.back())) break; nc.pop_back(); } if (nc.size() < row.size()) nc.push_back(cc); } #ifdef BALBIT #endif return smawk(row, nc); }else{ vector<int> odds; for (int i = 1; i<SZ(row); i += 2) { odds.pb(row[i]); } vector<int> pos = smawk(odds, col); pos.pb(col.back()); vector<int> ret; int j = 0; for (int i = 0; i<SZ(row); i++) { if (i & 1) { ret.pb(pos[i/2]); }else{ ret.pb(col[j]); ll mybest = 1e18+2; for (int k = j; k < SZ(col) && col[k] >= pos[i/2]; ++k) { ll cc = C(row[i], col[k]); if (cc < mybest) { mybest = cc; ret.back() = col[k]; } j=k; } RE = min(RE, mybest); } } return ret; } } signed main(){ IOS(); int k; cin>>k>>n; ll re = 0; map<int, int> hv; for (int i = 0; i<n; ++i) { char x, x2; int l, r; cin>>x>>l>>x2>>r; re += abs(r-l); if (x == x2) { }else{ if (r < l) swap(l,r); v.pb({l,r}); rbs.pb(r); lbs.pb(l); hv[l]--; hv[r]--; } } n = SZ(v); lhistory.pb(0); rhistory.pb(0); sort(ALL(v), [&](pii a, pii b){return a.f>b.f;}); vector<ll> fff; for (int i = 0; i<n; ++i) { fff.pb(v[i].f + v[i].s); } sort(ALL(fff)); for (int i = 0; i<n; ++i) { segmp[fff[i]] = i; } segmp[-1]=-1; build(lhistory.back(), 0, 1e5+3); for (int i = 0; i<n; ++i) { int topb = T_cnt; int tmp = lhistory.back(); MO(tmp, 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].f); lhistory.pb(topb); } sort(ALL(v), [&](pii a, pii b){return a.s<b.s;}); build(rhistory.back(), 0, 1e5+3); bug(rhistory.back()); for (int i = 0; i<n; ++i) { // if (v[i].s == 6) bug(v[i].s, v[i].f+v[i].s); int topb = T_cnt; int tmp = rhistory.back(); MO(tmp, 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].s); rhistory.pb(topb); } bug(rhistory.back()); sort(ALL(rbs)); sort(ALL(lbs)); lrev = lbs; sort(ALL(lrev), greater<int>()); for (int i = 0; i<n; ++i) { rps[i+1] = rps[i] + rbs[i]; lps[i+1] = lps[i] + lbs[i]; } if (k == 1) { ll now = lps[n]; bug(now); ll ans = now; ll x = 0; ll frt = n; for (pii ele : hv) { ll X = ele.f; now -= (X-x) * (frt); bug(X, now); ans = min(ans, now); frt += ele.s; x=X; } cout<<re + ans*2 + n<<endl; }else{ m = SZ(hv); p.resize(m); RE = C(0,0); int _it = 0; vector<int> r; for (pii ele : hv) { p[_it++] = ele.f; r.pb(ele.f); bug(ele.f); } vector<int> c = r; reverse(ALL(c)); reverse(ALL(r)); #ifdef BALBIT for (int i = 0; i<SZ(r); ++i) { for (int j = 0; j<SZ(c); ++j) { cout<<C(r[i],c[j])<<' '; } cout<<endl; } #endif vector<int> lol = smawk(r,c); for (int x : lol) bug(x); bug(RE); cout<<re + RE*2 + n<<endl; } } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:297:18: warning: unused variable 'x' [-Wunused-variable]
         for (int x : lol) bug(x);
                  ^
#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...