oj.uz

Submission #644299

# Submission time Handle Problem Language Result Execution time Memory
644299 2022-09-24T10:59:19 Z kingfran1907 Measures (CEOI22_measures) C++14
100 / 100
 911 ms 84480 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

struct node {
	llint sol;
	llint maxi, mini;
	int cnt;

	node(llint val) {
		maxi = mini = val;
		sol = 0, cnt = 1;
	}
	node() {sol = -1; maxi = mini = 0; cnt = 0;}

	void add(llint x) {
		maxi += x;
		mini += x;
	}
	void activate(llint val) {
		sol = 0;
		maxi = mini = val;
		cnt = 1;
	}
};

int n, m, d;
int a[maxn], b[maxn];
vector< int > v;
node tour[treesiz];
llint prop[treesiz];
map< int, int > cnt;

node merg(node a, node b) {
	if (a.sol == -1) return b;
	if (b.sol == -1) return a;

	node out;
	out.sol = max(a.sol, b.sol);
	out.sol = max(out.sol, b.maxi - a.mini);

	out.mini = min(a.mini, b.mini);
	out.maxi = max(a.maxi, b.maxi);
	out.cnt = a.cnt + b.cnt;
	return out;
}

void send(int x) {
	tour[x * 2].add(prop[x]);
	tour[x * 2 + 1].add(prop[x]);

	prop[x * 2] += prop[x];
	prop[x * 2 + 1] += prop[x];
	prop[x] = 0;
}

void update(int a, int b, int l, int r, int node, llint val) {
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		tour[node].add(val);
		prop[node] += val;
		return;
	}

	int mid = (l + r) / 2;
	send(node);
	update(a, b, l, mid, node * 2, val);
	update(a, b, mid + 1, r, node * 2 + 1, val);
	tour[node] = merg(tour[node * 2], tour[node * 2 + 1]);
} 

node query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return ::node();
	if (l >= a && r <= b) return tour[node];

	int mid = (l + r) / 2;
	send(node);
	return merg(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

int main() {
	scanf("%d%d%d", &n, &m, &d);
	for (int i = 0; i < n; i++)
		scanf("%d", a+i);
	for (int i = 0; i < m; i++)
		scanf("%d", b+i);

	sort(a, a + n);
	for (int i = 0; i < n; i++) v.push_back(a[i]);
	for (int i = 0; i < m; i++) v.push_back(b[i]);
	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++) {
		int ind = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		ind += cnt[a[i]]++;
		//printf("adding: %d\n", ind);
		tour[off + ind].sol = 0, tour[off + ind].cnt = 1;
		update(ind, ind, 0, off - 1, 1, (llint)i * d - a[i]);
	}
	for (int i = 0; i < m; i++) {
		int ind = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
		ind += cnt[b[i]]++;

		int prev = query(0, ind - 1, 0, off - 1, 1).cnt;
		//printf("adding: %d --> %d %lld\n", b[i], prev, (llint)prev * d - b[i]);
		llint kol = query(ind, ind, 0, off - 1, 1).maxi;
		tour[ind + off].activate(-kol);

		update(ind, ind, 0, off - 1, 1, (llint)prev * d - b[i]);
		//printf("debug: %lld %lld %lld\n", tour[1].maxi, tour[1].mini, tour[1].sol);
		update(ind + 1, off - 1, 0, off - 1, 1, d);

		llint out = tour[1].sol;
		//printf("debug: %lld %lld %lld\n", tour[1].maxi, tour[1].mini, tour[1].sol);
		printf("%lld", out / 2);
		if (out % 2 == 1) printf(".5");
		printf(" ");
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d%d%d", &n, &m, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
Main.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d", b+i);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66116 KB Output is correct
2 Correct 27 ms 66112 KB Output is correct
3 Correct 28 ms 65972 KB Output is correct
4 Correct 29 ms 66164 KB Output is correct
5 Correct 27 ms 66168 KB Output is correct
6 Correct 27 ms 66140 KB Output is correct
7 Correct 30 ms 66064 KB Output is correct
8 Correct 27 ms 66080 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66116 KB Output is correct
2 Correct 27 ms 66112 KB Output is correct
3 Correct 28 ms 65972 KB Output is correct
4 Correct 29 ms 66164 KB Output is correct
5 Correct 27 ms 66168 KB Output is correct
6 Correct 27 ms 66140 KB Output is correct
7 Correct 30 ms 66064 KB Output is correct
8 Correct 27 ms 66080 KB Output is correct
9 Correct 216 ms 81368 KB Output is correct
10 Correct 218 ms 81668 KB Output is correct
11 Correct 150 ms 71740 KB Output is correct
12 Correct 226 ms 81184 KB Output is correct
13 Correct 194 ms 80848 KB Output is correct
14 Correct 214 ms 80948 KB Output is correct
15 Correct 217 ms 80828 KB Output is correct
16 Correct 199 ms 80328 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 82276 KB Output is correct
2 Correct 478 ms 84260 KB Output is correct
3 Correct 423 ms 74692 KB Output is correct
4 Correct 495 ms 81512 KB Output is correct
5 Correct 495 ms 83360 KB Output is correct
6 Correct 470 ms 82368 KB Output is correct
7 Correct 484 ms 83644 KB Output is correct
8 Correct 491 ms 82664 KB Output is correct
9 Correct 493 ms 82028 KB Output is correct
10 Correct 537 ms 84480 KB Output is correct
11 Correct 507 ms 82700 KB Output is correct
12 Correct 520 ms 84052 KB Output is correct
13 Correct 911 ms 81888 KB Output is correct
14 Correct 492 ms 84164 KB Output is correct
15 Correct 500 ms 83764 KB Output is correct
16 Correct 483 ms 82008 KB Output is correct
17 Correct 475 ms 83344 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 82276 KB Output is correct
2 Correct 478 ms 84260 KB Output is correct
3 Correct 423 ms 74692 KB Output is correct
4 Correct 495 ms 81512 KB Output is correct
5 Correct 495 ms 83360 KB Output is correct
6 Correct 470 ms 82368 KB Output is correct
7 Correct 484 ms 83644 KB Output is correct
8 Correct 491 ms 82664 KB Output is correct
9 Correct 493 ms 82028 KB Output is correct
10 Correct 537 ms 84480 KB Output is correct
11 Correct 507 ms 82700 KB Output is correct
12 Correct 520 ms 84052 KB Output is correct
13 Correct 911 ms 81888 KB Output is correct
14 Correct 492 ms 84164 KB Output is correct
15 Correct 500 ms 83764 KB Output is correct
16 Correct 483 ms 82008 KB Output is correct
17 Correct 475 ms 83344 KB Output is correct
18 Correct 676 ms 83036 KB Output is correct
19 Correct 659 ms 84128 KB Output is correct
20 Correct 439 ms 75500 KB Output is correct
21 Correct 522 ms 82528 KB Output is correct
22 Correct 583 ms 82972 KB Output is correct
23 Correct 485 ms 82620 KB Output is correct
24 Correct 686 ms 83124 KB Output is correct
25 Correct 473 ms 82696 KB Output is correct
26 Correct 668 ms 82248 KB Output is correct
27 Correct 675 ms 84284 KB Output is correct
28 Correct 564 ms 82860 KB Output is correct
29 Correct 612 ms 82752 KB Output is correct
30 Correct 511 ms 81856 KB Output is correct
31 Correct 509 ms 84140 KB Output is correct
32 Correct 495 ms 83128 KB Output is correct
33 Correct 676 ms 80956 KB Output is correct
34 Correct 515 ms 82500 KB Output is correct