Submission #1088482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088482		Sunbae	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	33 ms	3508 KiB

bridge

#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
typedef long long ll;
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5, M = 2e5 + 5;
int a[M], m, cp[M], to_rem[N];
bool ok[N];
ll bit[2][M];
pii P[N], V[M];
int pos(int x){ return upper_bound(cp, cp+m, x) - cp;}
ll upd(int x, int i, ll val){ for(; i<M; i+=i&-i) bit[x][i] += val;}
ll qry(int x, int i){ ll res = 0; for(; i; i-=i&-i) res += bit[x][i]; return res;}
int _find(int k){
	int sum = 0, i = 0;
	for(int j = 18; j>=0; --j){
		if(i+(1<<j) < M && sum + bit[0][i+(1<<j)] < k) sum += bit[0][i+=(1<<j)];
	}
	return i + 1;
}

signed main(){
	int k, n; m = 0; scanf("%d %d", &k, &n);
	if(k == 1){
		ll tot = 0; char c[2];
		for(int i = 0, p[2]; i<n; ++i){
			scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
			if(c[0] == c[1]) tot += p[1] - p[0];
			else{ a[m++] = p[0]; a[m++] = p[1];}
		}
		sort(a, a+m);
		for(int i = 0; i<m; ++i) tot += abs(a[i] - a[m/2 - 1]);
		printf("%lld", tot + m/2);
	}else{
		ll tot = 0, sum[2] = {0, 0};
		for(int i = 0, p[2]; i<n; ++i){
			char c[2]; 
			scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
			if(c[0] == c[1]) tot += p[1] - p[0];
			else{
				cp[m] = p[0]; V[m++] = mp(p[0], i);
				cp[m] = p[1]; V[m++] = mp(p[1], i);
				P[i] = mp(p[0], p[1]);
				ok[i] = true;
				++tot;
			}
		}
		int sz = m, cnt = 0;
		sort(cp, cp+m); m = unique(cp, cp+m) - cp;
		sort(V, V+sz);
		for(int i = 0; i<n; ++i){
			if(ok[i]){
				int idx[2] = {pos(P[i].F), pos(P[i].S)};
				upd(0, idx[0], +1); upd(0, idx[1], +1);
				upd(1, idx[0], +P[i].F); upd(1, idx[1], +P[i].S);
				cnt += 2;
			}
		}
		int I = _find((cnt+1)/2);
		ll fp = qry(0, I) * cp[I-1] - qry(1, I);
		ll sp = (qry(1, M-1) - qry(1, I)) - (qry(0, M-1) - qry(0, I)) * cp[I-1];
		ll md = fp + sp, not_md = 0, mn = 2e18;
		set<int> s;
		for(int i = 0, j; i<sz; ){
			int t = 0;
			for(j = i; V[j].F == V[i].F; ++j){
				if(s.find(V[j].S) == s.end()){
					s.insert(V[j].S);
					int idx[2] = {pos(P[V[j].S].F), pos(P[V[j].S].S)};
					upd(0, idx[0], -1); upd(0, idx[1], -1); 
					upd(1, idx[0], -P[i].F); upd(1, idx[1], -P[i].S);
					cnt -= 2;
					not_md += P[V[j].S].S - P[V[j].S].F;
				}else{
					to_rem[t++] = V[j].S;
				}
				
			}
			//
			I = _find((cnt+1)/2);
			fp = qry(0, I) * cp[I-1] - qry(1, I);
			sp = (qry(1, M-1) - qry(1, I)) - (qry(0, M-1) - qry(0, I)) * cp[I-1];
			md = fp + sp;
			mn = min(mn, md + not_md);
			//
			for(int w = 0; w<t; ++w){
				s.erase(to_rem[w]);
				int idx[2] = {pos(P[to_rem[j]].F), pos(P[to_rem[j]].S)};
				upd(0, idx[0], +1); upd(0, idx[1], +1); 
				upd(1, idx[0], +P[i].F); upd(1, idx[1], +P[i].S);
				cnt += 2;
				not_md -= P[to_rem[w]].S - P[to_rem[w]].F;
			}
			//
			i = j;
		}
		printf("%lld", tot + mn);
	}
}

Compilation message (stderr)

bridge.cpp: In function 'll upd(int, int, ll)':
bridge.cpp:14:68: warning: no return statement in function returning non-void [-Wreturn-type]
   14 | ll upd(int x, int i, ll val){ for(; i<M; i+=i&-i) bit[x][i] += val;}
      |                                                                    ^
bridge.cpp: In function 'int main()':
bridge.cpp:37:15: warning: unused variable 'sum' [-Wunused-variable]
   37 |   ll tot = 0, sum[2] = {0, 0};
      |               ^~~
bridge.cpp:25:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  int k, n; m = 0; scanf("%d %d", &k, &n);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |    scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:40:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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