oj.uz

Submission #922588

# Submission time Handle Problem Language Result Execution time Memory
922588 2024-02-05T17:20:06 Z Nonoze Palembang Bridges (APIO15_bridge) C++17
100 / 100
 716 ms 221408 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 1512 KB Output is correct
5 Correct 2 ms 2532 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 2532 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1512 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 860 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 1512 KB Output is correct
5 Correct 3 ms 3040 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 2532 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1512 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 44 ms 4400 KB Output is correct
13 Correct 221 ms 138064 KB Output is correct
14 Correct 63 ms 4964 KB Output is correct
15 Correct 109 ms 70028 KB Output is correct
16 Correct 47 ms 4564 KB Output is correct
17 Correct 155 ms 136376 KB Output is correct
18 Correct 75 ms 21736 KB Output is correct
19 Correct 120 ms 72308 KB Output is correct
20 Correct 51 ms 3792 KB Output is correct
21 Correct 74 ms 22652 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 992 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 992 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 992 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 988 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 6 ms 4576 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 1504 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 6 ms 4832 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 4 ms 2788 KB Output is correct
23 Correct 2 ms 348 KB Output is correct
24 Correct 3 ms 1008 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 992 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 992 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 6 ms 4572 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 1504 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 6 ms 4744 KB Output is correct
21 Correct 2 ms 856 KB Output is correct
22 Correct 4 ms 2700 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 2 ms 1004 KB Output is correct
25 Correct 123 ms 4712 KB Output is correct
26 Correct 136 ms 4304 KB Output is correct
27 Correct 385 ms 76032 KB Output is correct
28 Correct 716 ms 220972 KB Output is correct
29 Correct 681 ms 218712 KB Output is correct
30 Correct 353 ms 116856 KB Output is correct
31 Correct 132 ms 4044 KB Output is correct
32 Correct 405 ms 221408 KB Output is correct
33 Correct 187 ms 42304 KB Output is correct
34 Correct 340 ms 128092 KB Output is correct
35 Correct 133 ms 4816 KB Output is correct
36 Correct 197 ms 42956 KB Output is correct
37 Correct 125 ms 4680 KB Output is correct