oj.uz

Submission #730639

# Submission time Handle Problem Language Result Execution time Memory
730639 2023-04-26T08:25:43 Z baojiaopisu Measures (CEOI22_measures) C++14
59 / 100
 1160 ms 53224 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 <= 55; 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 340 KB Output is correct
2 Correct 9 ms 428 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 8 ms 436 KB Output is correct
6 Correct 8 ms 436 KB Output is correct
7 Correct 9 ms 432 KB Output is correct
8 Correct 8 ms 432 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct
2 Correct 9 ms 428 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 8 ms 436 KB Output is correct
6 Correct 8 ms 436 KB Output is correct
7 Correct 9 ms 432 KB Output is correct
8 Correct 8 ms 432 KB Output is correct
9 Correct 996 ms 6732 KB Output is correct
10 Correct 1130 ms 6604 KB Output is correct
11 Correct 881 ms 6668 KB Output is correct
12 Correct 1160 ms 6608 KB Output is correct
13 Correct 835 ms 6616 KB Output is correct
14 Correct 977 ms 6604 KB Output is correct
15 Correct 963 ms 6668 KB Output is correct
16 Correct 852 ms 6604 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 49232 KB Output is correct
2 Correct 834 ms 51020 KB Output is correct
3 Correct 830 ms 53144 KB Output is correct
4 Correct 714 ms 50880 KB Output is correct
5 Correct 752 ms 52000 KB Output is correct
6 Correct 721 ms 51112 KB Output is correct
7 Correct 799 ms 52188 KB Output is correct
8 Correct 798 ms 50916 KB Output is correct
9 Correct 738 ms 50780 KB Output is correct
10 Correct 821 ms 53224 KB Output is correct
11 Correct 805 ms 51672 KB Output is correct
12 Correct 789 ms 52584 KB Output is correct
13 Correct 801 ms 50800 KB Output is correct
14 Correct 806 ms 52784 KB Output is correct
15 Correct 812 ms 52624 KB Output is correct
16 Correct 742 ms 50500 KB Output is correct
17 Correct 771 ms 52220 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 49232 KB Output is correct
2 Correct 834 ms 51020 KB Output is correct
3 Correct 830 ms 53144 KB Output is correct
4 Correct 714 ms 50880 KB Output is correct
5 Correct 752 ms 52000 KB Output is correct
6 Correct 721 ms 51112 KB Output is correct
7 Correct 799 ms 52188 KB Output is correct
8 Correct 798 ms 50916 KB Output is correct
9 Correct 738 ms 50780 KB Output is correct
10 Correct 821 ms 53224 KB Output is correct
11 Correct 805 ms 51672 KB Output is correct
12 Correct 789 ms 52584 KB Output is correct
13 Correct 801 ms 50800 KB Output is correct
14 Correct 806 ms 52784 KB Output is correct
15 Correct 812 ms 52624 KB Output is correct
16 Correct 742 ms 50500 KB Output is correct
17 Correct 771 ms 52220 KB Output is correct
18 Incorrect 922 ms 51296 KB Output isn't correct
19 Halted 0 ms 0 KB -