oj.uz

Submission #730635

# Submission time Handle Problem Language Result Execution time Memory
730635 2023-04-26T08:17:09 Z baojiaopisu Measures (CEOI22_measures) C++14
24 / 100
 1119 ms 53020 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e15;
const int N = 5e5 + 10;

ld a[N], p[N], b[N];
pair<ld, int> f[N];
int id[N];

struct SegTree {
	struct Node {
		ld ma = -INF;
		ld mi = INF;
		ld lazy = 0;
	};
	int n;
	vector<Node> node;

	SegTree(int _n = 0) {
		n = _n;
		node.resize(4 * n + 7);
	}
private:
	Node merge(const Node &a, const Node &b) {
		Node ans = Node();
		ans.ma = max(a.ma, b.ma);
		ans.mi = min(a.mi, b.mi);
		return ans;
	}

	void Down(int id) {
		ld x = node[id].lazy;
		node[id].lazy = 0;

		for(int i = (id << 1); i <= (id << 1 | 1); i++) {
			node[i].ma += x;
			node[i].mi += x;
			node[i].lazy += x;
		}
	}

	void Add(int l, int r, int lo, int hi, ld val, int id) {
		if(l > hi || r < lo) return;
		if(lo <= l && r <= hi) {
			node[id].ma += val;
			node[id].mi += val;
			node[id].lazy += val;
			return;
		}

		Down(id);
		int mid = (l + r) >> 1;
		Add(l, mid, lo, hi, val, id << 1);
		Add(mid + 1, r, lo, hi, val, id << 1 | 1);
		node[id] = merge(node[id << 1], node[id << 1 | 1]);
	}

	void Update(int l, int r, int pos, ld val, int id) {
		if(l == r) {
			node[id].ma = node[id].mi = val;
			return;
		}

		Down(id);
		int mid = (l + r) >> 1;
		if(pos <= mid) Update(l, mid, pos, val, id << 1);
		else Update(mid + 1, r, pos, val, id << 1 | 1);
		node[id] = merge(node[id << 1], node[id << 1 | 1]);
	}

	Node Get(int l, int r, int lo, int hi, int id) {
		if(l > hi || r < lo) return Node();
		if(lo <= l && r <= hi) return node[id];

		Down(id);
		int mid = (l + r) >> 1;
		Node left = Get(l, mid, lo, hi, id << 1);
		Node right = Get(mid + 1, r, lo, hi, id << 1 | 1);
		return merge(left, right);
	}
public:
	void update(int pos, ld val) {
		Update(1, n, pos, val, 1);
	}

	void add(int l, int r, ld val) {
		Add(1, n, l, r, val, 1);
	}

	ld getMin(int l, int r) {
		Node ans = Get(1, n, l, r, 1);
		return ans.mi;
	}

	ld getMax(int l, int r) {
		Node ans = Get(1, n, l, r, 1);
		return ans.ma;
	}
};

void BaoJiaoPisu() {
	int n, m; ld d; cin >> n >> m >> d;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> b[i];
	cout << fixed;
	cout << setprecision(1);
	if(m <= 10) {
		for(int t = 1; t <= m; t++) {
			a[++n] = b[t];
			sort(a + 1, a + 1 + n);
			ld l = 0, r = 1e14, ans = 0;
			for(int rep = 1; rep <= 52; rep++) {
				bool ok = true;
				ld mid = (l + r) / 2;
				p[1] = a[1] - mid;
				for(int i = 2; i <= n; i++) {
					p[i] = max(p[i - 1] + d, a[i] - mid);
					if(p[i] > a[i] + mid) {
						ok = false;
						break;
					}
				}

				if(ok) {
					ans = mid;
					r = mid;
				} else l = mid;
			}
			ll res = ans;
			ld tt = ans - res;
			if(tt < 1.0 / 2) cout << res << " ";
			else cout << ans << ' ';
		}
		return;
	}

	assert(n == 0);
	n = m;
	for(int i = 1; i <= n; i++) f[i] = mp(b[i], i);
	sort(f + 1, f + 1 + n);
	SegTree IT = SegTree(n);

	for(int i = 1; i <= n; i++) {
		id[f[i].se] = i;
	}

	ld ans = 0;
	for(int i = 1; i <= n; i++) {
		int p = id[i];
		ld left = IT.getMax(1, p - 1);
		ld right = IT.getMin(1, p + 1);
		ld l = 0, r = 1e15, res = 0;
		for(int rep = 1; rep <= 60; rep++) {
			ld mid = (l + r) / 2;
			ld p = left - mid + d;
			if(p - b[i] > ans + mid) {
				l = mid;
			} else {
				r = res = mid;
			}
		}

		ll tmp = res;
		ld tt = res - tmp;
		if(tt < 1.0 / 2) res = tmp;
		else res = 1.0 * tmp + 1.0 / 2;
		ans += res;
		tmp = ans;
		tt = ans - tmp;
		if(tt < 1.0 / 2) cout << tmp << " ";
		else cout << ans << ' ';
		IT.add(1, p - 1, -res);
		left -= res;
		ld c = max(left + d, b[i] - ans);
		IT.update(p, c);
	}
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        BaoJiaoPisu();
    }
}

Compilation message

Main.cpp: In function 'void BaoJiaoPisu()':
Main.cpp:16:15: warning: unused variable 'ANH' [-Wunused-variable]
   16 | #define right ANH
      |               ^~~
Main.cpp:217:6: note: in expansion of macro 'right'
  217 |   ld right = IT.getMin(1, p + 1);
      |      ^~~~~
Main.cpp: In function 'int main()':
Main.cpp:249:17: warning: unused variable 'ddd' [-Wunused-variable]
  249 |     int tc = 1, ddd = 0;
      |                 ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 452 KB Output is correct
2 Correct 9 ms 452 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 11 ms 456 KB Output is correct
5 Correct 9 ms 344 KB Output is correct
6 Correct 9 ms 340 KB Output is correct
7 Correct 12 ms 340 KB Output is correct
8 Correct 9 ms 452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 452 KB Output is correct
2 Correct 9 ms 452 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 11 ms 456 KB Output is correct
5 Correct 9 ms 344 KB Output is correct
6 Correct 9 ms 340 KB Output is correct
7 Correct 12 ms 340 KB Output is correct
8 Correct 9 ms 452 KB Output is correct
9 Correct 970 ms 8660 KB Output is correct
10 Correct 1117 ms 7884 KB Output is correct
11 Correct 879 ms 7888 KB Output is correct
12 Correct 1119 ms 7884 KB Output is correct
13 Correct 821 ms 7884 KB Output is correct
14 Correct 942 ms 7884 KB Output is correct
15 Correct 970 ms 7868 KB Output is correct
16 Correct 845 ms 7896 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 51284 KB Output is correct
2 Incorrect 811 ms 53020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 51284 KB Output is correct
2 Incorrect 811 ms 53020 KB Output isn't correct
3 Halted 0 ms 0 KB -