Submission #582489

#	Time	Username	Problem	Language	Result	Execution time	Memory
582489		NekoRolly	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	3 ms	4948 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define upp(a, b) upper_bound(b.begin(), b.end(), a) - b.begin()
typedef long long ll;
const int N = 2e5+4;
const ll inf = 4e18;

struct node{
	ll a,b,c;
};

node operator+(node a,node b){
	return {a.a + b.a, a.b + b.b, a.c + b.c};
}

struct St{
	int n;
	node t[N<<2];

	void build(int _n){ n = _n;
		for (int i=1; i<2*n; i++) t[i] = {0, 0, 0};
	}

	void up(int i,node val){ i+=n;
		for (t[i] = t[i] + val; i>>=1; ) t[i] = t[i<<1] + t[i<<1|1];
	}

	node que(int l,int r){ node ans = {0, 0, 0};
		for (l+=n, r+=n; l<r; l>>=1, r>>=1){
			if (l&1) ans = ans + t[l++];
			if (r&1) ans = ans + t[--r];
		}
		return ans;
	}
} d3;

int k,n,n1,n2;
ll ans1,ans2;
pair<int,int> a1[N];
vector<int> d1,d2[N];
ll pr[N],Spr[N],su[N],Ssu[N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> k >> n; ans2 = inf;

	for (int l,r; n; n--){ char cl,cr; cin >> cl >> l >> cr >> r;
		if (l > r) swap(l, r); ans1 += r-l;
		if (cl != cr) a1[n1++] = {l, r};
	}

	ans1 += n1;

	for (int i=0; i<n1; i++){ auto [l, r] = a1[i];
		d1.push_back(l), d1.push_back(r);
	}

	sort(d1.begin(), d1.end());
	d1.erase(unique(d1.begin(), d1.end()), d1.end());
	n2 = d1.size();

	for (int i=0; i<n1; i++){ auto [l, r] = a1[i];
		d2[upp(r, d1)].push_back(upp(l, d1));
		pr[upp(r, d1)]++, su[upp(l, d1)]++, Spr[upp(r, d1)] += r, Ssu[upp(l, d1)] += l;
	}

	for (int i=1; i<=n2; i++) pr[i] += pr[i-1], Spr[i] += Spr[i-1];
	for (int i=n2; i>=1; i--) su[i] += su[i+1], Ssu[i] += Ssu[i+1];

	// for (int i=1; i<=n2; i++) cout << d1[i-1] << " "; cout << "\n";


	// for (int i=1; i<=n2; i++)
		// cout << i << " -> " << pr[i] << " " << Spr[i] << " " << su[i] << " " << Ssu[i] << "\n";

	if (k == 1)	for (int i=1; i<=n2; i++)
		ans2 = min(ans2, Ssu[i+1] - Spr[i-1] + d1[i-1]*(pr[i-1] - su[i+1]));
	else for (int i=1; i+1<=n2; i++){ vector<int> d4;
		for (int j=i+1; j<=n2; j++) for (int l : d2[j-1]) if (l > i) 
			d4.push_back(d1[l-1] + d1[j-2]);
		sort(d4.begin(), d4.end());
		d4.erase(unique(d4.begin(), d4.end()), d4.end());
		d3.build(d4.size());
		for (int j=i+1; j<=n2; j++){
			for (int l : d2[j-1]) if (l > i)
				d3.up(upp(d1[l-1] + d1[j-2], d4)-1, {1, d1[l-1], d1[j-2]});
			node x = d3.que(0, upp(d1[i-1] + d1[j-1], d4));
			node y = d3.que(upp(d1[i-1] + d1[j-1], d4), d3.n);
			ans2 = min(ans2, x.b - d1[i-1]*x.a + d1[j-1]*y.a - y.c);
		}
	}

	// cout << ans1 << " " << ans2 << "\n";
	cout << ans1 + 2*ans2 << "\n";

    return 0;
}

/*

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:49:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |   if (l > r) swap(l, r); ans1 += r-l;
      |   ^~
bridge.cpp:49:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |   if (l > r) swap(l, r); ans1 += r-l;
      |                          ^~~~

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