Submission #1291174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291174		kustov_vadim_533	Horses (IOI15_horses)	C++20	100 / 100	127 ms	48356 KiB

horses

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <array>
#include <map>
#include <random>
#include <bitset>
#include <stack>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <chrono>

using namespace std;

typedef long long ll;
typedef long double ld;

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

const int M = 1e9 + 7;

struct obj {
	int ans = 1, x = 1, y = 1, suf = 1;
	bool fans = false, fx = false, fsuf = false;

	obj() = default;

	obj(int x, int y) : x(x), y(y) {
		ans = (x * 1ll * y) % M;
		fans = x * 1ll * y >= M;
	}
};


obj merge(obj a, obj b) {
	obj c;
	c.x = (a.x * 1ll * b.x) % M;
	c.fx = a.fx || b.fx || (a.x * 1ll * b.x >= M);

	if (!a.fsuf && !b.fans && a.y > a.suf * 1ll * b.ans) {
		c.ans = a.ans;
		c.fans = a.fans;
		
		c.y = a.y;

		c.suf = (a.suf * 1ll * b.x) % M;
		c.fsuf = a.fsuf || b.fx || (a.suf * 1ll * b.x >= M);
	}
	else {
		c.ans = (b.ans * 1ll * a.x) % M;
		c.fans = b.fans || a.fans || (b.ans * 1ll * a.x >= M);

		c.y = b.y;

		c.suf = b.suf;
		c.fsuf = b.fsuf;
	}
	return c;
}

vector<obj> tree;
vector<int> Xi, Yi;

void build(int v, int l, int r) {
	if (r - l == 1) {
		tree[v] = obj(Xi[l], Yi[l]);
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}


int n;
int init(int N, int X[], int Y[]) {
	tree.resize(4 * N);
	n = N;

	Xi.resize(n);
	Yi.resize(n);

	for (int i = 0; i < N; ++i) {
		Xi[i] = X[i];
		Yi[i] = Y[i];
	}
	build(1, 0, N);
	return tree[1].ans;
}

void upd(int v, int l, int r, int qi) {
	if (r - l == 1) {
		tree[v] = obj(Xi[l], Yi[l]);
		return;
	}
	int m = (l + r) / 2;
	if (qi < m) upd(v * 2, l, m, qi);
	else upd(v * 2 + 1, m, r, qi);
	tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}

int updateX(int pos, int val) {
	Xi[pos] = val;
	upd(1, 0, n, pos);
	return tree[1].ans;
}


int updateY(int pos, int val) {
	Yi[pos] = val;
	upd(1, 0, n, pos);
	return tree[1].ans;
}

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