oj.uz

답안 #553349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553349 2022-04-25T14:33:18 Z yoavL Palembang Bridges (APIO15_bridge) C++14
63 / 100
 304 ms 208684 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -