oj.uz

Submission #317874

# Submission time Handle Problem Language Result Execution time Memory
317874 2020-10-30T16:30:29 Z parsabahrami Palembang Bridges (APIO15_bridge) C++17
100 / 100
 727 ms 24828 KB 
//! God Is Dead
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define sonic(x)  					sort(all(x)); x.resize(unique(all(x)) - (x).begin());

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 2e5 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
ll n, k, fen[MAXN], A[MAXN], B[MAXN], L[MAXN], R[MAXN], sum = 0, ans = 0;
Tree<pair<pll, ll>> st; vector<ll> compress = {-INF}; vector<pair<pll, ll>> vec;

void update(ll id, ll x) {
	for (; id < MAXN; id += id & -id) {
		fen[id] += x;
	}
}

ll get(ll pos, ll res = 0) {
	for (; pos; pos -= pos & -pos) {
		res += fen[pos];
	}
	return res;
}

int main() {
	scanf("%lld%lld", &k, &n);
	for (ll i = 1; i <= n; i++) {
		char s[2]; scanf("%s%lld%s%lld", s, &A[i], s + 1, &B[i]);
		if (s[0] == s[1]) sum += abs(A[i] - B[i]);
		else {
			sum++;
			vec.push_back({{A[i], B[i]}, i}); compress.push_back(A[i]);
			compress.push_back(B[i]);
		}
	}
	sonic(compress);
	sort(all(vec), [&](pair<pll, ll> x, pair<pll, ll> y) {
		return x.F.F + x.F.S < y.F.F + y.F.S;
	});
	n = sz(vec); if (n == 0) return !printf("%lld\n", sum);
	for (ll i = 1; i <= n; i++) {
		ll l = vec[i - 1].F.F, r = vec[i - 1].F.S, id = vec[i - 1].S;
		ll pl = lower_bound(all(compress), l) - compress.begin();
		ll pr = lower_bound(all(compress), r) - compress.begin();
		update(pl, l);
		update(pr, r);
		st.insert({{l, id}, 1});
		st.insert({{r, id}, 2});
		ll median = (st.find_by_order((sz(st) + 1) / 2)->F).F;
		ll pm = lower_bound(all(compress), median) - compress.begin();
		L[i] = median * st.order_of_key({{median, MOD}, 3}) - get(pm);
		L[i] += get(MAXN - 1) - get(pm) - median * (sz(st) - st.order_of_key({{median, MOD}, 3}));
	}
	memset(fen, 0, sizeof fen);
	if (k == 1) return !printf("%lld\n", L[n] + sum);
	st.clear();
	for (ll i = n; i; i--) {
		ll l = vec[i - 1].F.F, r = vec[i - 1].F.S, id = vec[i - 1].S;
		ll pl = lower_bound(all(compress), l) - compress.begin();
		ll pr = lower_bound(all(compress), r) - compress.begin();
		update(pl, l);
		update(pr, r);
		st.insert({{l, id}, 1});
		st.insert({{r, id}, 2});
		ll median = (st.find_by_order((sz(st) + 1) / 2)->F).F;
		ll pm = lower_bound(all(compress), median) - compress.begin();
		R[i] = median * st.order_of_key({{median, MOD}, 3}) - get(pm);
		R[i] += get(MAXN - 1) - get(pm) - median * (sz(st) - st.order_of_key({{median, MOD}, 3}));
	}
	ans = L[1] + R[2];
	for (ll i = 1; i < n; i++)  {
		ans = min(ans, L[i] + R[i + 1]);
	}
	printf("%lld\n", ans + sum);
    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%lld%lld", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
bridge.cpp:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   char s[2]; scanf("%s%lld%s%lld", s, &A[i], s + 1, &B[i]);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 2176 KB Output is correct
4 Correct 3 ms 2176 KB Output is correct
5 Correct 3 ms 2048 KB Output is correct
6 Correct 3 ms 2176 KB Output is correct
7 Correct 3 ms 2176 KB Output is correct
8 Correct 3 ms 2176 KB Output is correct
9 Correct 3 ms 2176 KB Output is correct
10 Correct 3 ms 2176 KB Output is correct
11 Correct 3 ms 2176 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 2176 KB Output is correct
4 Correct 3 ms 2176 KB Output is correct
5 Correct 3 ms 2176 KB Output is correct
6 Correct 3 ms 2176 KB Output is correct
7 Correct 3 ms 2176 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 3 ms 2176 KB Output is correct
10 Correct 3 ms 2176 KB Output is correct
11 Correct 3 ms 2176 KB Output is correct
12 Correct 165 ms 23804 KB Output is correct
13 Correct 410 ms 23800 KB Output is correct
14 Correct 268 ms 21628 KB Output is correct
15 Correct 187 ms 14992 KB Output is correct
16 Correct 165 ms 23804 KB Output is correct
17 Correct 221 ms 23932 KB Output is correct
18 Correct 187 ms 23804 KB Output is correct
19 Correct 237 ms 23764 KB Output is correct
20 Correct 164 ms 23932 KB Output is correct
21 Correct 234 ms 23800 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 2 ms 1920 KB Output is correct
7 Correct 2 ms 1920 KB Output is correct
8 Correct 2 ms 1920 KB Output is correct
9 Correct 2 ms 1920 KB Output is correct
10 Correct 2 ms 2048 KB Output is correct
11 Correct 2 ms 1920 KB Output is correct
12 Correct 2 ms 1920 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 1 ms 1920 KB Output is correct
7 Correct 2 ms 1920 KB Output is correct
8 Correct 2 ms 2048 KB Output is correct
9 Correct 2 ms 1920 KB Output is correct
10 Correct 2 ms 1920 KB Output is correct
11 Correct 2 ms 1920 KB Output is correct
12 Correct 2 ms 2048 KB Output is correct
13 Correct 3 ms 2176 KB Output is correct
14 Correct 4 ms 2176 KB Output is correct
15 Correct 4 ms 2176 KB Output is correct
16 Correct 3 ms 1920 KB Output is correct
17 Correct 3 ms 2048 KB Output is correct
18 Correct 2 ms 2048 KB Output is correct
19 Correct 3 ms 2176 KB Output is correct
20 Correct 4 ms 2176 KB Output is correct
21 Correct 4 ms 2176 KB Output is correct
22 Correct 4 ms 2304 KB Output is correct
23 Correct 3 ms 2176 KB Output is correct
24 Correct 4 ms 2176 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 1 ms 1952 KB Output is correct
7 Correct 2 ms 1920 KB Output is correct
8 Correct 2 ms 1920 KB Output is correct
9 Correct 2 ms 2048 KB Output is correct
10 Correct 2 ms 1920 KB Output is correct
11 Correct 2 ms 1920 KB Output is correct
12 Correct 2 ms 1920 KB Output is correct
13 Correct 3 ms 2176 KB Output is correct
14 Correct 4 ms 2176 KB Output is correct
15 Correct 4 ms 2176 KB Output is correct
16 Correct 2 ms 1920 KB Output is correct
17 Correct 3 ms 2048 KB Output is correct
18 Correct 2 ms 2048 KB Output is correct
19 Correct 3 ms 2176 KB Output is correct
20 Correct 4 ms 2176 KB Output is correct
21 Correct 4 ms 2304 KB Output is correct
22 Correct 4 ms 2176 KB Output is correct
23 Correct 3 ms 2176 KB Output is correct
24 Correct 4 ms 2080 KB Output is correct
25 Correct 308 ms 24696 KB Output is correct
26 Correct 535 ms 24572 KB Output is correct
27 Correct 715 ms 24688 KB Output is correct
28 Correct 709 ms 24704 KB Output is correct
29 Correct 727 ms 24728 KB Output is correct
30 Correct 301 ms 14088 KB Output is correct
31 Correct 317 ms 24572 KB Output is correct
32 Correct 361 ms 24828 KB Output is correct
33 Correct 321 ms 24572 KB Output is correct
34 Correct 380 ms 24700 KB Output is correct
35 Correct 288 ms 24716 KB Output is correct
36 Correct 368 ms 24700 KB Output is correct
37 Correct 261 ms 24572 KB Output is correct