Submission #238141

#	Time	Username	Problem	Language	Result	Execution time	Memory
238141		wwdd	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	578 ms	44004 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<pl> vpl;
class ST {
	private:
		ll n;
		int h;
		vl st;
	public:
		ST(int n_) {
			h = 1;n = 1;
			while(n < n_) {
				n <<= 1;
				h++;
			}
			st.assign(2*n,0);
		}
		void up(ll p, ll val) {
			p += n;
			st[p] += val;
			while(p > 1) {
				st[p>>1] = st[p] + st[p^1];
				p >>= 1;
			}
		}
		ll get(int l, int r) {
			ll res = 0;
			for(l += n,r += n;l<r;l>>=1,r>>=1) {
				if(l&1) {
					res += st[l];
					l++;
				}
				if(r&1) {
					--r;
					res += st[r];
				}
			}
			return res;
		}
		int kth(int u) {
			int p = 1;
			for(int i=1;i<h;i++) {
				p <<= 1;
				if(st[p] < u) {
					u -= st[p];p++;
				}
			}
			return p-n;
		}
		inline ll size() {return n;}
};
vpl w;
ll wol() {
	vl wa;
	sort(w.begin(),w.end(),[&](const pl& a, const pl& b) {
			return a.first + a.second < b.first + b.second;
			});
	for(int i=0;i<w.size();i++) {
		wa.push_back(w[i].first);
		wa.push_back(w[i].second);
	}
	map<ll,ll> mu;
	sort(wa.begin(),wa.end());
	for(int i=0;i<wa.size();i++) {
		mu[wa[i]] = i;
	}
	vl rac(w.size()+1,0);
	int rid = 0;
	ST sa(wa.size()),sb(wa.size()),ra(wa.size()),rb(wa.size()),kt(wa.size());
	ll res = 1e18;
	for(int i=0;i<w.size();i++) {
		int ia = mu[w[i].first];
		int ib = mu[w[i].second];
		sa.up(ib,w[i].second);
		sb.up(ib,1);
		kt.up(ib,1);
		ra.up(ia,w[i].first);
		rb.up(ia,1);
		kt.up(ia,1);
		int mi = kt.kth(i+1);
		ll x = wa[mi];
		rac[i+1] += 2*(x*sb.get(0,mi)-sa.get(0,mi) + ra.get(mi,ra.size()) - x*rb.get(mi,rb.size()));
	}
	sa = ST(wa.size());
	sb = ST(wa.size());
	ra = ST(wa.size());
	rb = ST(wa.size());
	kt = ST(wa.size());
	for(int i=w.size()-1;i>=0;i--) {
		int ia = mu[w[i].first];
		int ib = mu[w[i].second];
		sa.up(ib,w[i].second);
		sb.up(ib,1);
		kt.up(ib,1);
		ra.up(ia,w[i].first);
		rb.up(ia,1);
		kt.up(ia,1);
		int mi = kt.kth(w.size()-i);
		ll x = wa[mi];
		rac[i] += 2*(x*sb.get(0,mi)-sa.get(0,mi) + ra.get(mi,ra.size()) - x*rb.get(mi,rb.size()));
	}
	for(int i=0;i<rac.size();i++) {
		res = min(res,rac[i]);
	}
	return res;
}
ll lol() {
	vl wa;
	for(int i=0;i<w.size();i++) {
		wa.push_back(w[i].first);
		wa.push_back(w[i].second);
	}
	sort(wa.begin(),wa.end());
	ll pos = wa[wa.size()/2];
	ll res = 0;
	for(int i=0;i<w.size();i++) {
		res += abs(w[i].first-pos) + abs(pos-w[i].second);
	}
	return res;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int k,n;
	cin >> k >> n;
	ll wad = 0;
	ll nev = 0;
	for(int i=0;i<n;i++) {
		char ca,cb;
		ll a,b;
		cin >> ca >> a >> cb >> b;
		if(ca == cb) {
			wad += abs(a-b);
		} else {
			wad++;
			nev += max(a,b)-min(a,b);
			w.push_back({min(a,b),max(a,b)});
		}
	}
	sort(w.begin(),w.end());
	ll res = -1;
	if(k == 1) {
		res = lol();
	} else {
		res = wol();
		res += nev;
	}
	cout << res+wad << '\n';
}

Compilation message (stderr)

bridge.cpp: In function 'll wol()':
bridge.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();i++) {
              ~^~~~~~~~~
bridge.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<wa.size();i++) {
              ~^~~~~~~~~~
bridge.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();i++) {
              ~^~~~~~~~~
bridge.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rac.size();i++) {
              ~^~~~~~~~~~~
bridge.cpp:71:6: warning: unused variable 'rid' [-Wunused-variable]
  int rid = 0;
      ^~~
bridge.cpp: In function 'll lol()':
bridge.cpp:112:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();i++) {
              ~^~~~~~~~~
bridge.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();i++) {
              ~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37