oj.uz

Submission #477347

# Submission time Handle Problem Language Result Execution time Memory
477347 2021-10-01T17:49:14 Z ymm Palembang Bridges (APIO15_bridge) C++17
100 / 100
 150 ms 9036 KB 
///
///   ♪ Let the voice of love take you higher! ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define F first
#define S second
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

ll inf = 1e9+100;
const int N = 100010;
pll a[N];
int k, n;

vector<ll> stb;
ll cntl[2*N], cntr[2*N];

#ifndef EVAL
void dbg(){cout << "!\n";}
template<class T, class... U> void dbg(T x, U... y){cout << x << ' '; dbg(y...);}
#else
template<class... T> void dbg(T... x){}
#endif

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	#ifndef EVAL
	freopen("in.txt", "r", stdin);
	#endif
	cin >> k >> n;
	ll stoneocean = 0;
	Loop(i,0,n)
	{
		char c1,c2; ll a1,a2;
		cin >> c1 >> a1;
		cin >> c2 >> a2;
		if(c1==c2)
		{
			stoneocean += abs(a1-a2);
			--i; --n;
		}
		else
		{
			a[i] = {a1,a2};
			stb.push_back(a1);
			stb.push_back(a2);
			stoneocean += 1;
		}
	}
	if(n == 0) return cout << stoneocean << '\n', 0;
	sort(stb.begin(),stb.end());
	stb.resize(unique(stb.begin(),stb.end())-stb.begin());
	Loop(i,0,n)
		cntr[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]++,
		cntr[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]++;
	sort(a,a+n,[](pll& x, pll& y){return x.F+x.S < y.F+y.S;});
	int p1 = 0, p2 = 0;
	ll c1 = 0, c2 = 2*n - 2*cntr[0];
	ll suml = 0, sumr = -2*n*stb[0]; Loop(i,0,n) sumr += a[i].F+a[i].S;
	while(c2 > 0) {
		sumr -= c2*(stb[p2+1]-stb[p2]);
		++p2;
		c2 -= 2*cntr[p2];
	}
	if(k==1) return cout << stoneocean+sumr << '\n', 0;
	auto mov = [&](int i) -> void{
		sumr -= abs(a[i].F-stb[p2]);
		sumr -= abs(a[i].S-stb[p2]);
		suml += abs(a[i].F-stb[p1]);
		suml += abs(a[i].S-stb[p1]);
		c2 -= a[i].F <= stb[p2]? -1: 1;
		c2 -= a[i].S <= stb[p2]? -1: 1;
		c1 += a[i].F <= stb[p1]? -1: 1;
		c1 += a[i].S <= stb[p1]? -1: 1;
		cntr[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]--;
		cntl[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]++;
		cntr[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]--;
		cntl[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]++;
	};
	ll ans = suml+sumr;
	Loop(i,0,n)
	{
		mov(i);
		while(c2 > 0) {
			sumr -= c2*(stb[p2+1]-stb[p2]);
			++p2;
			c2 -= 2*cntr[p2];
		}
		while(c1 > 0) {
			suml -= c1*(stb[p1+1]-stb[p1]);
			++p1;
			c1 -= 2*cntl[p1];
		}
		ans = min(ans, suml+sumr);
	}
	cout << stoneocean+ans << '\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 28 ms 3528 KB Output is correct
13 Correct 86 ms 5052 KB Output is correct
14 Correct 64 ms 3528 KB Output is correct
15 Correct 51 ms 3224 KB Output is correct
16 Correct 46 ms 3520 KB Output is correct
17 Correct 46 ms 5028 KB Output is correct
18 Correct 52 ms 5136 KB Output is correct
19 Correct 84 ms 4984 KB Output is correct
20 Correct 37 ms 3552 KB Output is correct
21 Correct 63 ms 5108 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 33 ms 3528 KB Output is correct
26 Correct 54 ms 4444 KB Output is correct
27 Correct 139 ms 8156 KB Output is correct
28 Correct 150 ms 8960 KB Output is correct
29 Correct 138 ms 9036 KB Output is correct
30 Correct 70 ms 4908 KB Output is correct
31 Correct 37 ms 5228 KB Output is correct
32 Correct 76 ms 8920 KB Output is correct
33 Correct 88 ms 8668 KB Output is correct
34 Correct 127 ms 8856 KB Output is correct
35 Correct 39 ms 5440 KB Output is correct
36 Correct 91 ms 8784 KB Output is correct
37 Correct 29 ms 4360 KB Output is correct