oj.uz

답안 #29378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29378 2017-07-19T07:52:32 Z Namnamseo Palembang Bridges (APIO15_bridge) C++14
22 / 100
 69 ms 18276 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int k, n;
vector<pp> d;
ll ans_base;

void in(){
	read(k, n);
	for(int i=1; i<=n; ++i){
		char p, q;
		int s, t;
		auto f = [](){char t; do{t=getchar();}while(t!='A'&&t!='B'); return t;};
		p = f(); read(s);
		q = f(); read(t);
		if(p == q){
			ans_base += abs(s - t);
		} else {
			++ans_base;
			d.eb(min(s, t), max(s, t));
		}
	}
	n = d.size();
}

ll dp1[100010];
ll dp2[100010];

struct SEG {
	const static int M = 262144;
	ll tree[M<<1];
	void init(){ memset(tree, 0, sizeof(tree)); }
	void upd(int p, ll v){for(p+=M;p;p/=2)tree[p]+=v;}
	ll s(int l,int r){
		ll ret=0;
		l+=M; r+=M;
		while(l<=r){
			if(l&1) ret+=tree[l++];
			if(r%2==0) ret+=tree[r--];
			l>>=1; r>>=1;
		}
		return ret;
	}
} sc, sl, sr;

int pt[200010], ptn;
priority_queue<int> pq;
void Work(ll dp[100010]){
	sc.init();
	sl.init();
	sr.init();
	while(pq.size()) pq.pop();
	auto add = [&](int a){
		pq.push(a);
		int b = lower_bound(pt, pt+ptn, a) - pt;
		sc.upd(b, 1);
		sl.upd(b, -a);
		sr.upd(b, a);
	};
	for(int i=1; i<=n; ++i){
		add(d[i-1].x);
		add(d[i-1].y);
		pq.pop();
		int mid = pq.top();
		int p = lower_bound(pt, pt+ptn, mid) - pt;
		dp[i] = sc.s(0, p-1) * mid + sl.s(0, p-1) + 
			sr.s(p+1, ptn-1) - sc.s(p+1, ptn-1) * mid;
	}
}

int main()
{
	in();
	for(auto tmp:d) pt[ptn++]=tmp.x, pt[ptn++]=tmp.y;
	sort(pt, pt+ptn);
	if(k == 1){
		ll ans=0; int p=pt[n];
		for(auto tmp:d) ans += abs(tmp.x-p) + abs(tmp.y-p);
		printf("%lld\n", ans + ans_base);
		return 0;
	}
	ptn=unique(pt,pt+ptn)-pt;
	sort(all(d), [&](const pp& a, const pp& b){
		return a.x+a.y < b.x+b.y;
	});
	Work(dp1);
	reverse(all(d));
	Work(dp2); reverse(dp2, dp2+n+1);
	ll ans = 1LL << 60;
	for(int i=0; i<=n; ++i){
		ans = min(ans, dp1[i] + dp2[i]);
	}
	printf("%lld\n", ans + ans_base);
	return 0;
}

Compilation message

bridge.cpp: In function 'void read(int&)':
bridge.cpp:6:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^
bridge.cpp: In function 'void read(ll&)':
bridge.cpp:7:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                                   ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16656 KB Output is correct
2 Correct 0 ms 16656 KB Output is correct
3 Correct 0 ms 16656 KB Output is correct
4 Correct 0 ms 16656 KB Output is correct
5 Correct 0 ms 16656 KB Output is correct
6 Correct 0 ms 16656 KB Output is correct
7 Correct 0 ms 16656 KB Output is correct
8 Correct 0 ms 16656 KB Output is correct
9 Correct 0 ms 16656 KB Output is correct
10 Correct 0 ms 16656 KB Output is correct
11 Correct 0 ms 16656 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16656 KB Output is correct
2 Correct 0 ms 16656 KB Output is correct
3 Correct 0 ms 16656 KB Output is correct
4 Correct 0 ms 16656 KB Output is correct
5 Correct 0 ms 16656 KB Output is correct
6 Correct 0 ms 16656 KB Output is correct
7 Correct 0 ms 16656 KB Output is correct
8 Correct 0 ms 16656 KB Output is correct
9 Correct 0 ms 16656 KB Output is correct
10 Correct 0 ms 16656 KB Output is correct
11 Correct 0 ms 16656 KB Output is correct
12 Correct 29 ms 18276 KB Output is correct
13 Correct 69 ms 18276 KB Output is correct
14 Correct 43 ms 18276 KB Output is correct
15 Correct 39 ms 17508 KB Output is correct
16 Correct 33 ms 18276 KB Output is correct
17 Correct 43 ms 18276 KB Output is correct
18 Correct 53 ms 18276 KB Output is correct
19 Correct 56 ms 18276 KB Output is correct
20 Correct 53 ms 18276 KB Output is correct
21 Correct 49 ms 18276 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 16656 KB Output is correct
2 Correct 3 ms 16656 KB Output is correct
3 Correct 0 ms 16656 KB Output is correct
4 Incorrect 3 ms 16656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16656 KB Output is correct
2 Correct 0 ms 16656 KB Output is correct
3 Correct 3 ms 16656 KB Output is correct
4 Incorrect 3 ms 16656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16656 KB Output is correct
2 Correct 3 ms 16656 KB Output is correct
3 Correct 6 ms 16656 KB Output is correct
4 Incorrect 3 ms 16656 KB Output isn't correct
5 Halted 0 ms 0 KB -