Submission #1291670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291670		ortsac	Horses (IOI15_horses)	C++20	100 / 100	903 ms	54276 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;

struct Big {
	int curr = 1;
	bool big = 0;
};

Big segb[4*MAXN];
int x[MAXN], y[MAXN];
int n;

Big multb(Big a, Big b) {
	Big ans;
	int x = (a.curr * b.curr);
	ans.big = (a.big || b.big);
	ans.big |= (x >= MOD);
	x %= MOD;
	ans.curr = x;
	return ans;
}

void buildb(int node, int l, int r) {
	if (l == r) {
		segb[node].curr = x[l];
		segb[node].big = 0;
		return;
	}
	int m = (l + r)/2;
	buildb(2*node, l, m);
	buildb(2*node + 1, m + 1, r);
	segb[node] = multb(segb[2*node], segb[2*node + 1]);
}

void updateb(int node, int l, int r, int po) {
	if (l == r) {
		segb[node].curr = x[l];
		segb[node].big = 0;
		return;
	}
	int m = (l + r)/2;
	if (po <= m) updateb(2*node, l, m, po);
	else updateb(2*node + 1, m + 1, r, po);
	segb[node] = multb(segb[2*node], segb[2*node + 1]);
}

Big queryb(int node, int l, int r, int tl, int tr) {
	if ((tl <= l) && (r <= tr)) return segb[node];
	if ((r < tl) || (tr < l)) return Big();
	int m = (l + r)/2;
	return multb(queryb(2*node, l, m, tl, tr), queryb(2*node + 1, m + 1, r, tl, tr));
}

struct Node {
	int val = 0, totmult = 1, po = 0;
};

Node merge(Node a, Node b) {
	Node ans;
	// ok, check which side is better
	int l = a.po + 1, r = b.po;
	Big isbig = queryb(1, 1, n, l, r);
	Big onlyy;
	onlyy.curr = y[b.po];
	onlyy.big = 0;
	isbig = multb(isbig, onlyy);
	ans.totmult = ((a.totmult * b.totmult) % MOD);
	if (isbig.big || (isbig.curr > y[a.po])) {
		ans.po = b.po;
		ans.val = ((a.totmult * b.val) % MOD);
		return ans;
	}
	ans.po = a.po;
	ans.val = a.val;
	return ans;
}

Node seg[4*MAXN];

void build(int node, int l, int r) {
	if (l == r) {
		seg[node].po = l;
		seg[node].val = ((x[l]*y[l]) % MOD);
		seg[node].totmult = x[l];
		return;
	}
	int m = (l + r)/2;
	build(2*node, l, m);
	build(2*node + 1, m + 1, r);
	seg[node] = merge(seg[2*node], seg[2*node + 1]);
}

void update(int node, int l, int r, int po) {
	if (l == r) {
		seg[node].po = l;
		seg[node].val = ((x[l]*y[l]) % MOD);
		seg[node].totmult = x[l];
		return;
	}
	int m = (l + r)/2;
	if (po <= m) update(2*node, l, m, po);
	else update(2*node + 1, m + 1, r, po);
	seg[node] = merge(seg[2*node], seg[2*node + 1]);
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
	n = N;
	for (int i = 1; i <= n; i++) x[i] = X[i - 1];
	for (int i = 1; i <= n; i++) y[i] = Y[i - 1];
	buildb(1, 1, n);
	build(1, 1, n);
	return seg[1].val;
}

int32_t updateX(int32_t pos, int32_t val) {
	pos++;
	x[pos] = val;
	updateb(1, 1, n, pos);
	update(1, 1, n, pos);
	return seg[1].val;
}

int32_t updateY(int32_t pos, int32_t val) {
	pos++;
	y[pos] = val;
	update(1, 1, n, pos);
	return seg[1].val;
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23