Submission #553344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553344	2022-04-25T14:15:17 Z	yoavL	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	1038 ms	262144 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 (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));
		}
	}
	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()) {
      |  ^~~
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++)
......
  322 |   rep(j, i + 1, vals.size()) {
      |       ~~~~~~~~~~~~~~~~~~~~~           
bridge.cpp:322:3: note: in expansion of macro 'rep'
  322 |   rep(j, i + 1, 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	3 ms	1748 KB	Output is correct
5	Correct	4 ms	1620 KB	Output is correct
6	Correct	2 ms	600 KB	Output is correct
7	Correct	4 ms	1744 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	1752 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 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	1748 KB	Output is correct
5	Correct	3 ms	1620 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	2 ms	1748 KB	Output is correct
8	Correct	3 ms	1620 KB	Output is correct
9	Correct	3 ms	1748 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	3 ms	1744 KB	Output is correct
12	Correct	57 ms	33364 KB	Output is correct
13	Correct	323 ms	204568 KB	Output is correct
14	Correct	199 ms	127404 KB	Output is correct
15	Correct	202 ms	115992 KB	Output is correct
16	Correct	57 ms	33124 KB	Output is correct
17	Correct	235 ms	208740 KB	Output is correct
18	Correct	250 ms	199380 KB	Output is correct
19	Correct	246 ms	207172 KB	Output is correct
20	Correct	59 ms	33120 KB	Output is correct
21	Correct	265 ms	208760 KB	Output is correct

Subtask #3

9.0 / 9.0

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

Subtask #4

32.0 / 32.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	0 ms	340 KB	Output is correct
4	Correct	6 ms	1108 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	9 ms	1364 KB	Output is correct
9	Correct	9 ms	468 KB	Output is correct
10	Correct	8 ms	1108 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	8 ms	852 KB	Output is correct
13	Correct	1 ms	596 KB	Output is correct
14	Correct	4 ms	1876 KB	Output is correct
15	Correct	963 ms	63024 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	5 ms	1492 KB	Output is correct
18	Correct	146 ms	11032 KB	Output is correct
19	Correct	2 ms	596 KB	Output is correct
20	Correct	1030 ms	95608 KB	Output is correct
21	Correct	792 ms	2292 KB	Output is correct
22	Correct	904 ms	71092 KB	Output is correct
23	Correct	2 ms	596 KB	Output is correct
24	Correct	969 ms	44012 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	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	6 ms	1108 KB	Output is correct
5	Correct	3 ms	724 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	8 ms	1364 KB	Output is correct
9	Correct	6 ms	456 KB	Output is correct
10	Correct	7 ms	1032 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	8 ms	852 KB	Output is correct
13	Correct	1 ms	592 KB	Output is correct
14	Correct	5 ms	1876 KB	Output is correct
15	Correct	931 ms	62900 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	4 ms	1492 KB	Output is correct
18	Correct	148 ms	10896 KB	Output is correct
19	Correct	1 ms	592 KB	Output is correct
20	Correct	1038 ms	95580 KB	Output is correct
21	Correct	772 ms	2356 KB	Output is correct
22	Correct	810 ms	71008 KB	Output is correct
23	Correct	2 ms	596 KB	Output is correct
24	Correct	848 ms	43928 KB	Output is correct
25	Correct	62 ms	33868 KB	Output is correct
26	Correct	131 ms	79652 KB	Output is correct
27	Runtime error	473 ms	262144 KB	Execution killed with signal 9
28	Halted	0 ms	0 KB	-