Submission #433389

#	Time	Username	Problem	Language	Result	Execution time	Memory
433389		ngpin04	Circus (Balkan15_CIRCUS)	C++14	100 / 100	1343 ms	25140 KiB

circus

#include <bits/stdc++.h>
#include "circus.h"
//#include "grader.cpp"
#define fi first
#define se second
#define mp make_pair		
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int Nmax = 1e5 + 5; 	
const int oo = 1e9;

vector <int> a;
vector <int> fval, gval;

int mx[Nmax << 2];
int mn[Nmax << 2];

int d[Nmax][2];
int dp[Nmax];
int n,m;

void solve() {
	priority_queue <pair <int, pair <int, int>>> heap;
	for (int i = 0; i <= n; i++)
	for (int j = 0; j < 2; j++)
		d[i][j] = oo;
	d[n][0] = 0;
	heap.push(mp(0, mp(n, 0)));
	while (heap.size()) {
		int cur = -heap.top().fi;
		int i = heap.top().se.fi;
		int dir = heap.top().se.se;
		heap.pop();
		if (d[i][dir] != cur)
			continue;
		int j = i + ((dir == 0) ? -1 : 1);
		if (j >= 0 && j <= n && mini(d[j][dir], cur + abs(a[i] - a[j]))) 
			heap.push(mp(-d[j][dir], mp(j, dir)));

		j = lower_bound(a.begin(), a.end(), a[i] + cur) - a.begin();
		if (j <= n && mini(d[j][1], a[j] - a[i]))
			heap.push(mp(-d[j][1], mp(j, 1)));

		j = upper_bound(a.begin(), a.end(), a[i] - cur) - a.begin() - 1;
		if (j >= 0 && mini(d[j][0], a[i] - a[j]))
			heap.push(mp(-d[j][0], mp(j, 0)));
	}

	for (int i = 0; i <= n; i++) {
		dp[i] = min(d[i][0], d[i][1]);
		// cerr << dp[i] << " \n"[i == n];
	}
}

void update(int id, int l, int r, int pos, pair <int, int> val) {
	if (l > pos || r < pos)
		return;
	if (l == r)
		return (void) (mini(mn[id], val.fi), maxi(mx[id], val.se));
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, pos, val);
	update(id << 1 | 1, mid + 1, r, pos, val);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
	mn[id] = min(mn[id << 1], mn[id << 1 | 1]); 
}

pair <int, int> get(int id, int l, int r, int u, int v) {
	if (l > v || r < u)
		return mp(oo, -oo);
	if (l >= u && r <= v)
		return mp(mn[id], mx[id]);
	int mid = (l + r) >> 1;
	pair <int, int> lnode = get(id << 1, l, mid, u, v);
	pair <int, int> rnode = get(id << 1 | 1, mid + 1, r, u, v);
	return mp(min(lnode.fi, rnode.fi), max(lnode.se, rnode.se));
}

void init(int N, int M, int P[]) {
	n = N;
	m = M;
	for (int i = 0; i < n; i++)
		a.push_back(P[i]);
	a.push_back(M);
	sort(a.begin(), a.end());
	solve();

	for (int i = 0; i <= n; i++) {
		fval.push_back(a[i] - dp[i]);
		gval.push_back(a[i] + dp[i]);
	}
	sort(fval.begin(), fval.end());
	fval.resize(unique(fval.begin(), fval.end()) - fval.begin());
	
	sort(gval.begin(), gval.end());
	gval.resize(unique(gval.begin(), gval.end()) - gval.begin());

	for (int i = 1; i <= ((n + 1) << 2); i++)
		mn[i] = oo, mx[i] = -oo;

	for (int i = 0; i <= n; i++) {
		int pos, val;
		val = a[i] - dp[i];
		pos = lower_bound(fval.begin(), fval.end(), val) - fval.begin();
		update(1, 0, n, pos, mp(a[i], -oo));
		
		val = a[i] + dp[i];
		pos = lower_bound(gval.begin(), gval.end(), val) - gval.begin();
		update(1, 0, n, pos, mp(oo, a[i]));
	}
}

int minLength(int x) {
	int pos;
	int res = oo;
	pos = lower_bound(fval.begin(), fval.end(), x) - fval.begin();
	res = get(1, 0, n, pos, n).fi - x;

	pos = upper_bound(gval.begin(), gval.end(), x) - gval.begin() - 1;
	if (pos >= 0) 
		mini(res, x - get(1, 0, n, 0, pos).se);

	return res;	
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &P[i]);
      |   ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9