Submission #922588

#	Time	Username	Problem	Language	Result	Execution time	Memory
922588		Nonoze	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	716 ms	221408 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long long ll;


#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()


struct node {
	int left, right;
	int sum, nb;
	node() {left=-1, right=-1, sum=0, nb=0;}
};


vector<vector<node>> st(2);

void create(int empl) {
	st[empl].push_back(node());
}

void updatte(int empl, int node) {
	int nb=0, sum=0;
	if (st[empl][node].left!=-1) nb+=st[empl][ st[empl][node].left ].nb, sum+=st[empl][ st[empl][node].left ].sum;
	if (st[empl][node].right!=-1) nb+=st[empl][ st[empl][node].right ].nb, sum+=st[empl][ st[empl][node].right ].sum;
	st[empl][node].nb=nb, st[empl][node].sum=sum;
}

void update(int empl, int node, int left, int right, int qval, int value) {
	if (left==right) {
		st[empl][node].nb+=value;
		st[empl][node].sum+=value*left;
		return;
	}
	int mid=(left+right)/2;
	if (mid>=qval) {
		if (st[empl][node].left==-1) {
			create(empl);
			st[empl][node].left=sz(st[empl])-1;
		}
		update(empl, st[empl][node].left, left, mid, qval, value);
	} else {
		if (st[empl][node].right==-1) {
			create(empl);
			st[empl][node].right=sz(st[empl])-1;
		}
		update(empl, st[empl][node].right, mid+1, right, qval, value);
	}
	updatte(empl, node);
}

int milieu;

int query(int empl, int node, int left, int right, int qval) {
	if (left==right) {
		milieu=left;
		return 0;
	}
	int mid=(left+right)/2;
	int ans=0;
	if (st[empl][node].left!=-1 && st[empl][ st[empl][node].left ].nb>=qval) {
		ans=query(empl, st[empl][node].left, left, mid, qval);
		if (st[empl][node].right!=-1) {
			ans+=st[empl][ st[empl][node].right ].sum-st[empl][ st[empl][node].right ].nb*milieu;
		}
	} else if (st[empl][node].right!=-1) {
		int moins=0;
		if (st[empl][node].left!=-1) moins=st[empl][ st[empl][node].left].nb;
		ans=query(empl, st[empl][node].right, mid+1, right, qval-moins);
		if (st[empl][node].left!=-1) {
			ans+=st[empl][ st[empl][node].left ].nb*milieu-st[empl][ st[empl][node].left ].sum;
		}
	}
	return ans;
}

struct traj {
	int l, r;
	double mid;
};

vector<traj> a;
int n, k, m;


void solve() {
	cin >> k >> n;
	int res=0;
	for (int i=0; i<n; i++) {
		char aa, bb;
		int aaa, bbb; cin >> aa >> aaa >> bb >> bbb;
		if (aa==bb) {
			res+=abs(aaa-bbb);
			continue;
		}
		if (aaa>bbb) swap(aaa, bbb);
		a.push_back(traj{aaa, bbb, (double)(aaa+bbb)/2.0});
	}
	n=sz(a);
	res+=n;
	if (n==0) {
		cout << res << endl;
		return;
	}
	sort(all(a), [](traj &A, traj &B){return A.mid<B.mid;});
	create(0), create(1);
	for (int i=0; i<n; i++) {
		update(0, 0, 0, (int)1e9, a[i].l, 1);
		update(0, 0, 0, (int)1e9, a[i].r, 1);
	}
	if (k==1) {
		cout << res+query(0, 0, 0, (int)1e9, n) << endl;
		return;
	}

	int ans=LLONG_MAX;
	for (int i=0; i<n; i++) {
		int s1=query(0, 0, 0, (int)1e9, (n-i));
		int s2=query(1, 0, 0, (int)1e9, i);
		ans=min(ans, s1+s2);
		update(0, 0, 0, (int)1e9, a[i].l, -1);
		update(0, 0, 0, (int)1e9, a[i].r, -1);
		update(1, 0, 0, (int)1e9, a[i].l, 1);
		update(1, 0, 0, (int)1e9, a[i].r, 1);
	}
	cout << res+ans << endl;	
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	return 0;
}

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