Submission #553349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553349	2022-04-25T14:33:18 Z	yoavL	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	304 ms	208684 KB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
#include <functional>
#include <numeric>
#include <chrono>
#include <random>

using namespace std;

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;

const ll inf = (ll)2e18;
const ll mod = (ll)(1e9 + 7);

#define FAST        ios_base::sync_with_stdio(0)
#define FASTIN		cin.tie(0)
#define FASTOUT		cout.tie(0)

#define upmin(a, b) (a) = min((a), (b))
#define upmax(a, b) (a) = max((a), (b))

#define pr(x) cout << x << endl
#define prv(v) for(auto it : v) cout << it << " "; cout << endl;
#define prvv(v) for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define spr(x) cout << x << " "

//#define DBG_FLAG (1) // Toggle to switch between bebug mode and solution mode
#ifdef DBG_FLAG
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": " << endl; for(auto& it : v) cout << it << " "; cout << endl;
#define wprvv(v) cout << #v << ": " << endl; for(auto& it : v) { for(auto& it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define wspr(x) cout << #x << ": " << x << " "
#endif

#ifndef DBG_FLAG
#define wpr(x)
#define wprv(v)
#define wprvv(v)
#define wspr(x)
#endif

#define x first
#define y second
#define rep(i, s, e) for(ll i = s; i < e; i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back

/*

Solution:
Let's start with k == 1:

Make a presistent segment tree.
Now, for each one we try, we have to take all values that end before it,
and all values that start after it.

*/


ostream& operator<<(ostream& os, const pll& p)
{
	os << "{" << p.x << ", " << p.y << "}";
	return os;
}

template <typename T, typename U>
pair<T, U> operator+(const pair<T, U>& l, const pair<T, U>& r) {
	return { l.first + r.first, l.second + r.second };
}

vll vals;
struct tr {
	//int l, r, m;
	int cnt;
	ll v;
	tr* lp = nullptr, * rp = nullptr;


	void push(ll l, ll r)
	{
		if (l == r) return;
		ll m = (l + r) / 2;
		if (!lp) {
			lp = new tr(l, m);
		}
		if (!rp) {
			rp = new tr(m + 1, r);
		}
	}
	void pull(ll l, ll r)
	{
		if (l == r) return;
		cnt = (lp ? lp->cnt : 0) + (rp ? rp->cnt : 0);
		v = (lp ? lp->v : 0) + (rp ? rp->v : 0);
	}
	tr() {}
	tr(tr* other) : cnt(other->cnt), v(other->v), lp(other->lp), rp(other->rp) {}
	//tr(ll l, ll r, ll v) : l(l), r(r), m((l+r)>>1), v(v) {}
	tr(ll l, ll r) : cnt(0), v(0)
	{
		/*
		if (l == r) return;
		lp = new tr(l, m);
		rp = new tr(m + 1, r);
		*/
	}
	void update(ll i, ll l, ll r) {
		if (l == r) {
			cnt++;
			v += i;
			return;
		}
		//push(l, r);
		ll m = (l + r) / 2;
		if (i <= m) {
			if (!lp) lp = new tr(l, m);
			lp = lp->add(i, l, m);
		}
		else {
			if (!rp) rp = new tr(m + 1, r);
			rp = rp->add(i, m + 1, r);
		}
		pull(l, r);
	}
	tr* add(ll i, ll l, ll r)
	{
		//push(l, r);
		tr* t = new tr(this);
		/*
		if (!lp&&!rp) {
			t->update(i, l, r);
			return t;
		}*/
		//if (!lp) return t;
		if (l == r) {
			t->cnt++;
			t->v += vals[i];
			return t;
			//return new tr(l, r, this->v + add);
		}
		ll m = (l + r) / 2;
		if (i <= m) {
			if (!lp) lp = new tr(l, m);
			t->lp = lp->add(i, l, m);
		}
		else {
			if (!rp) rp = new tr(m + 1, r);
			t->rp = rp->add(i, m + 1, r);
		}
		t->pull(l, r);
		return t;
	}

	pll q(ll f, ll t, ll l, ll r) {
		if (r < f || l > t) return { 0, 0 };
		if (f <= l && r <= t) return { cnt, v };
		push(l, r);
		ll m = (l + r) / 2;
		return lp->q(f, t, l, m) + rp->q(f, t, m + 1, r);
	}
};



const ll maxN = 1e5 + 5;
const ll maxV = 1e9 + 5;
ll k, n;
vpll segs;

ll sz;
ll ans = 0;

tr* segR[maxN], * segL[maxN];

void construct_pers_segs()
{
	sz = vals.size();

	segL[0] = new tr(0, sz);
	wpr("Left:");
	rep(i, 0, n) {
		ll ind = lower_bound(vals.begin(), vals.end(), segs[i].x) - vals.begin();
		wpr(ind);
		segL[i + 1] = segL[i]->add(ind, 0, sz);
	}
	segL[n + 1] = segL[n];
	if (k == 2 && n >= 1e4) return;
	segR[n + 1] = new tr(0, sz);
	wpr("Right:");
	for (ll i = n - 1; i >= 0; i--) {
		ll ind = lower_bound(vals.begin(), vals.end(), segs[i].y) - vals.begin();
		wpr(ind);
		segR[i + 1] = segR[i + 2]->add(ind, 0, sz);
	}
	segR[0] = segR[1];
}

bool comp_segs(const pll& p1, const pll& p2)
{
	return p1.x + p1.y < p2.x + p2.y;
}
ll calc_k1(ll i)
{
	ll cost = 0;
	pll l = segR[0]->q(0, i - 1, 0, sz);
	cost += (l.x * vals[i] - l.y) * 2;
	pll r = segL[n]->q(i + 1, sz, 0, sz);
	cost += (r.y - r.x * vals[i]) * 2;
	return cost;
}
ll calc_k2(ll i, ll j)
{
	if (i == 2 && j == 5) {
		//spr("---------");
		//cout << "Check Here" << endl;
		wpr(vals[i]);
		wpr(vals[j]);
	}
	wpr(i);
	wpr(j);
	ll cost = 0;

	pll l = segR[0]->q(0, i - 1, 0, sz);
	wpr(l);
	cost += (l.x * vals[i] - l.y) * 2;
	ll place = n;
	ll low = 0, high = n - (ll)1, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (segs[mid].x + segs[mid].y >= vals[i] + vals[j]) {
			upmin(place, mid);
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	wpr(place);
	//ll place = lower_bound(segs.begin(), segs.end(), pll{ vals[i], vals[j] }, comp_segs) - segs.begin();
	pll pt = segL[place]->q(i, j, 0, sz);
	wpr(pt);
	cost += (pt.y - pt.x * vals[i]) * 2;
	//place++;

	pt = segR[place + 1]->q(i, j, 0, sz);
	wpr(pt);

	cost += (pt.x * vals[j] - pt.y) * 2;
	pll r = segL[n]->q(j, sz, 0, sz);
	wpr(r);
	cost += (r.y - r.x * vals[j]) * 2;
	wpr(cost);
	return cost;
}
void solve_k1()
{
	ll minAdd = inf;
	/*
	rep(i, 0, vals.size()) {
		ll cost = calc_k1(i);
		upmin(minAdd, cost);
	}
	*/
	ll low = 0, high = vals.size() - (ll)1;
	while (low + 5 <= high) {
		ll m1 = low + (high - low) / 3;
		ll m2 = low + 2 * (high - low) / 3;
		ll v1 = calc_k1(m1);
		ll v2 = calc_k1(m2);
		upmin(minAdd, min(v1, v2));
		if (v1 <= v2) {
			high = m2;
		}
		else {
			low = m1;
		}
	}
	rep(i, low, high + 1) {
		upmin(minAdd, calc_k1(i));
	}
	ans += minAdd;
}


void solve_k2()
{
	ll minAdd = inf;
	rep(i, 0, vals.size()) {
		/*
		rep(j, i + 1, vals.size()) {
			upmin(minAdd, calc_k2(i, j));
		}
		*/
		/*
		rep(i, 0, vals.size()) {
			ll cost = calc_k1(i);
			upmin(minAdd, cost);
		}
		*/
		ll low = i + 1, high = vals.size() - (ll)1;
		while (low + 5 <= high) {
			ll m1 = low + (high - low) / 3;
			ll m2 = low + 2 * (high - low) / 3;
			ll v1 = calc_k2(i, m1);
			ll v2 = calc_k2(i, m2);
			upmin(minAdd, min(v1, v2));
			if (v1 <= v2) {
				high = m2;
			}
			else {
				low = m1;
			}
		}
		rep(j, low, high + 1) {
			upmin(minAdd, calc_k2(i, j));
		}
	}
	ans += minAdd;
}


void solve()
{
	cin >> k >> n;
	//vals.push_back(0);
	//vals.push_back(maxV);
	rep(i, 0, n) {
		char side1, side2;
		ll v1, v2;
		cin >> side1 >> v1 >> side2 >> v2;
		ans += max(v1, v2) - min(v1, v2);
		if (side1 == side2) continue;
		ans++;
		segs.push_back({ min(v1, v2), max(v1, v2) });
		vals.push_back(v1);
		vals.push_back(v2);

	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	wprv(vals);
	n = segs.size();
	wpr(n);
	sort(segs.begin(), segs.end(), [&](const pll& p1, const pll& p2) {
		return p1.x + p1.y < p2.x + p2.y;
		});
	wprv(segs);
	if (n <= 1) {

		pr(ans);
		return;
	}
	construct_pers_segs();
	if (k == 1) solve_k1();
	else solve_k2();
	pr(ans);

}


int main()
{
	FAST;
	FASTIN; FASTOUT;
	solve();

}


/*

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

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

*/

Compilation message

bridge.cpp: In function 'void solve_k2()':
bridge.cpp:77:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 | #define rep(i, s, e) for(ll i = s; i < e; i++)
......
  321 |  rep(i, 0, vals.size()) {
      |      ~~~~~~~~~~~~~~~~~                
bridge.cpp:321:2: note: in expansion of macro 'rep'
  321 |  rep(i, 0, vals.size()) {
      |  ^~~

Subtask #1

8.0 / 8.0

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

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	2 ms	1620 KB	Output is correct
5	Correct	2 ms	1620 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	3 ms	1748 KB	Output is correct
8	Correct	2 ms	1620 KB	Output is correct
9	Correct	2 ms	1748 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	2 ms	1748 KB	Output is correct
12	Correct	48 ms	33196 KB	Output is correct
13	Correct	304 ms	204448 KB	Output is correct
14	Correct	177 ms	127404 KB	Output is correct
15	Correct	167 ms	116148 KB	Output is correct
16	Correct	55 ms	33184 KB	Output is correct
17	Correct	224 ms	208648 KB	Output is correct
18	Correct	232 ms	199376 KB	Output is correct
19	Correct	245 ms	207180 KB	Output is correct
20	Correct	56 ms	33156 KB	Output is correct
21	Correct	243 ms	208684 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	2 ms	724 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	2 ms	596 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	2 ms	724 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	2 ms	596 KB	Output is correct
13	Correct	1 ms	596 KB	Output is correct
14	Correct	3 ms	1364 KB	Output is correct
15	Correct	35 ms	8772 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	2 ms	980 KB	Output is correct
18	Correct	10 ms	2644 KB	Output is correct
19	Correct	1 ms	596 KB	Output is correct
20	Correct	38 ms	11620 KB	Output is correct
21	Correct	25 ms	2136 KB	Output is correct
22	Correct	35 ms	8944 KB	Output is correct
23	Correct	1 ms	596 KB	Output is correct
24	Correct	31 ms	5204 KB	Output is correct

Subtask #5

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	2 ms	596 KB	Output is correct
13	Correct	1 ms	596 KB	Output is correct
14	Correct	2 ms	1364 KB	Output is correct
15	Correct	34 ms	8800 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	2 ms	980 KB	Output is correct
18	Correct	11 ms	2644 KB	Output is correct
19	Correct	1 ms	596 KB	Output is correct
20	Correct	39 ms	11580 KB	Output is correct
21	Correct	25 ms	2100 KB	Output is correct
22	Correct	36 ms	9008 KB	Output is correct
23	Correct	1 ms	596 KB	Output is correct
24	Correct	33 ms	5120 KB	Output is correct
25	Runtime error	52 ms	36928 KB	Execution killed with signal 11
26	Halted	0 ms	0 KB	-