Submission #644299

#	Time	Username	Problem	Language	Result	Execution time	Memory
644299		kingfran1907	Measures (CEOI22_measures)	C++14	100 / 100	911 ms	84480 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41