oj.uz

Submission #49937

# Submission time Handle Problem Language Result Execution time Memory
49937 2018-06-05T04:09:48 Z tmwilliamlin168 Palembang Bridges (APIO15_bridge) C++14
22 / 100
 160 ms 6848 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5;
int k, n, pts[2*mxN], med, ft2[2*mxN+1];
ll ba, ft1[2*mxN+1], a1[mxN+1], a2=LLONG_MAX;
vector<pii> ps;
priority_queue<int> bpq;
priority_queue<int, vector<int>, greater<int>> tpq;

inline void upd(int x) {
	if(x<med)
		bpq.push(x);
	else
		tpq.push(x);
	if(bpq.size()+2<=tpq.size()) {
		bpq.push(med);
		med=tpq.top(), tpq.pop();
	} else if(bpq.size()>=tpq.size()+2) {
		tpq.push(med);
		med=bpq.top(), bpq.pop();
	}
	for(int i=upper_bound(pts, pts+2*ps.size(), x)-pts; i<=2*ps.size(); i+=i&-i)
		ft1[i]+=x, ++ft2[i];
}

inline ll qry1(int x) {
	ll r=0;
	for(int i=upper_bound(pts, pts+2*ps.size(), x)-pts; i; i-=i&-i)
		r+=ft1[i];
	return r;
}

inline int qry2(int x) {
	int r=0;
	for(int i=upper_bound(pts, pts+2*ps.size(), x)-pts; i; i-=i&-i)
		r+=ft2[i];
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> k >> n;
	for(int i=0; i<n; ++i) {
		char z1, z2;
		pii pi;
		cin >> z1 >> pi.fi >> z2 >> pi.se;
		if(z1!=z2) {
			pts[2*ps.size()]=pi.fi, pts[2*ps.size()+1]=pi.se;
			ps.push_back(pi);
			++ba;
		} else
			ba+=abs(pi.fi-pi.se);
	}
	sort(pts, pts+2*ps.size());
	sort(ps.begin(), ps.end(), [](const pii &a, const pii &b) {
		return a.fi+a.se<b.fi+b.se;
	});
//	cout << "hi1" << endl;
	for(int i=0; i<ps.size(); ++i) {
		upd(ps[i].fi), upd(ps[i].se);
		a1[i+1]=(qry1(pts[2*ps.size()-1])-2*qry1(med))-(ll)med*(qry2(pts[2*ps.size()-1])-2*qry2(med));
	}
//	cout << "hi2" << endl;
	if(k==1) {
//		cout << ba+a1[3] << endl;
		cout << ba+a1[ps.size()];
		return 0;
	}
	memset(ft1, 0, 8*(2*ps.size()+1));
	memset(ft2, 0, 4*(2*ps.size()+1));
//	cout << "hi3" << endl;
	bpq=priority_queue<int>(), tpq=priority_queue<int, vector<int>, greater<int>>();
//	cout << "hi4" << endl;
	for(int i=ps.size()-1; i; --i) {
		upd(ps[i].fi), upd(ps[i].se);
		a2=min(a1[i]+(qry1(pts[2*ps.size()-1])-2*qry1(med))-(ll)med*(qry2(pts[2*ps.size()-1])-2*qry2(med)), a2);
	}
	cout << ba+a2;
}

Compilation message

bridge.cpp: In function 'void upd(int)':
bridge.cpp:28:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=upper_bound(pts, pts+2*ps.size(), x)-pts; i<=2*ps.size(); i+=i&-i)
                                                      ~^~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ps.size(); ++i) {
               ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 412 KB Output is correct
4 Correct 4 ms 700 KB Output is correct
5 Correct 3 ms 700 KB Output is correct
6 Correct 4 ms 700 KB Output is correct
7 Correct 4 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 3 ms 700 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 67 ms 4208 KB Output is correct
13 Correct 160 ms 6848 KB Output is correct
14 Correct 127 ms 6848 KB Output is correct
15 Correct 80 ms 6848 KB Output is correct
16 Correct 68 ms 6848 KB Output is correct
17 Correct 121 ms 6848 KB Output is correct
18 Correct 90 ms 6848 KB Output is correct
19 Correct 123 ms 6848 KB Output is correct
20 Correct 81 ms 6848 KB Output is correct
21 Correct 119 ms 6848 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 6848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -