oj.uz

답안 #553344

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

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

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

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

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

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