oj.uz

Submission #827216

# Submission time Handle Problem Language Result Execution time Memory
827216 2023-08-16T09:59:05 Z tranxuanbach Wiring (IOI17_wiring) C++17
25 / 100
 903 ms 231480 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())

using ll = long long;

const ll infll = (ll)1e18 + 7;

const int N = 2e5 + 5;

struct line_container{
	struct line_type{
		ll a, b;
		mutable ll p;
		bool operator< (const line_type& oth) const{
			return a < oth.a;
		}
		bool operator< (ll x) const{
			return p < x;
		}
	};

	multiset <line_type, less<>> mts;
	const ll inf = infll;

	ll div(ll x, ll y){
		return x / y - ((x ^ y) < 0 and x % y);
	}

	template <class T>
	bool isect(T x, T y){
		if (y == mts.end()){
			x->p = infll;
			return false;
		}
		if (x->a == y->a){
			x->p = x->b > y->b ? infll : -infll;
		}
		else{
			x->p = div(y->b - x->b, x->a - y->a);
		}
		return x->p >= y->p;
	}

	void insert(line_type l){
		l.a = -l.a; l.b = -l.b;
		auto z = mts.insert(l), y = z++, x = y;
		while (isect(y, z)){
			z = mts.erase(z);
		}
		if (x != mts.begin() and isect(--x, y)){
			isect(x, mts.erase(y));
		}
		while ((y = x) != mts.begin() and (--x)->p >= y->p){
			isect(x, mts.erase(y));
		}
	}

	ll query(ll x){
		if (mts.empty()){
			return infll;
		}
		auto l = *mts.lower_bound(x);
		return -(l.a * x + l.b);
	}
};

int n, m;
bool col[N];

pair <int, int> pre[N][2];
ll pref[N][2];
ll dp[N];

line_container seg[1 << 19];

void update(int id, int l, int r, int i, const line_container::line_type& ln){
	seg[id].insert(ln);
	if (l == r){
		return;
	}
	int mid = (l + r) >> 1;
	if (i <= mid){
		update(id * 2, l, mid, i, ln);
	}
	else{
		update(id * 2 + 1, mid + 1, r, i, ln);
	}
}

ll query(int id, int l, int r, int u, int v, ll x){
	if (v < l or r < u){
		return infll;
	}
	if (u <= l and r <= v){
		return seg[id].query(x);
	}
	int mid = (l + r) >> 1;
	return min(query(id * 2, l, mid, u, v, x), query(id * 2 + 1, mid + 1, r, u, v, x));
}

void update_dp(int i){
	update(1, 0, n + m, i, line_container::line_type{i, dp[i] + (ll)i * (i + 1) / 2});
}

ll min_total_length(vector <int> r, vector <int> b){
	n = isz(r);
	m = isz(b);
	for (auto pos: r){
		col[pos] = true;
	}
	for (auto pos: b){
		col[pos] = false;
	}
	pre[0][0] = pair{0, 0};
	pre[0][1] = pair{0, 0};
	ForE(i, 1, n + m){
		pre[i][0] = pre[i - 1][0];
		pre[i][1] = pre[i - 1][1];
		swap(pre[i][col[i]].fi, pre[i][col[i]].se);
		pre[i][col[i]].fi = i;
	}
	pref[0][0] = 0;
	pref[0][1] = 0;
	ForE(i, 1, n + m){
		pref[i][0] = pref[i - 1][0] + (col[i] == 0 ? i : 0);
		pref[i][1] = pref[i - 1][1] + (col[i] == 1 ? i : 0);
	}

	fill(dp, dp + n + m + 1, infll);
	dp[0] = 0;
	update_dp(0);
	ForE(i, 1, n + m){
		if (pre[i][0].fi == 0 or pre[i][1].fi == 0){
			continue;
		}
		int j = pre[i][col[i] ^ 1].fi;
		dp[i] = min(dp[i], i - j + dp[i - 1]);
		int k = pre[j][col[i]].fi;
		int leni = i - j, lenj = j - k;
		if (leni <= lenj){
			ll sum = (pref[i][col[i]] - pref[j][col[i]]) - (pref[j][col[i] ^ 1] - pref[j - leni][col[i] ^ 1]);
			int r = j - leni, l = k;
			// cout << l << ' ' << r << ' ' << query(1, 0, n + m, l, r, -(j + 1)) << endl;
			dp[i] = min(dp[i], sum + (ll)r * (j + 1) - (ll)r * (r + 1) / 2 + query(1, 0, n + m, l, r, -(j + 1)));
			// for (int x = j - leni; x >= k; x--){
			// 	dp[i] = min(dp[i], sum + dp[x]);
			// 	sum += (j + 1) - x;
			// }
		}
		// cout << "dp " << i << ' ' << dp[i] << endl;
		update_dp(i);
	}
	return dp[n + m];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 29012 KB 3rd lines differ - on the 1st token, expected: '25859', found: '1000000000000000007'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 29036 KB 3rd lines differ - on the 1st token, expected: '904', found: '26'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 29140 KB 3rd lines differ - on the 1st token, expected: '316', found: '36'
2 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28976 KB Output is correct
2 Correct 894 ms 231480 KB Output is correct
3 Correct 728 ms 183392 KB Output is correct
4 Correct 824 ms 214392 KB Output is correct
5 Correct 727 ms 183412 KB Output is correct
6 Correct 14 ms 29008 KB Output is correct
7 Correct 16 ms 28960 KB Output is correct
8 Correct 14 ms 29032 KB Output is correct
9 Correct 14 ms 29036 KB Output is correct
10 Correct 14 ms 29036 KB Output is correct
11 Correct 14 ms 28984 KB Output is correct
12 Correct 14 ms 29012 KB Output is correct
13 Correct 14 ms 29012 KB Output is correct
14 Correct 14 ms 29012 KB Output is correct
15 Correct 13 ms 29136 KB Output is correct
16 Correct 14 ms 29012 KB Output is correct
17 Correct 14 ms 29012 KB Output is correct
18 Correct 863 ms 208636 KB Output is correct
19 Correct 819 ms 210020 KB Output is correct
20 Correct 877 ms 220044 KB Output is correct
21 Correct 903 ms 225612 KB Output is correct
22 Correct 735 ms 193996 KB Output is correct
23 Correct 559 ms 163716 KB Output is correct
24 Correct 717 ms 186752 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 29012 KB 3rd lines differ - on the 1st token, expected: '25859', found: '1000000000000000007'
2 Halted 0 ms 0 KB -