Submission #1291135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291135		kustov_vadim_533	Horses (IOI15_horses)	C++20	0 / 100	217 ms	121572 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 x = 1, y = 1;
	ld mx = 1, my = 1;
};


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

	if (a.my > a.mx * b.my) {
		c.y = a.y;
		c.my = a.my;
	}
	else {
		c.y = (a.x * 1ll * b.y) % M;
		c.my = a.mx * b.my;
	}
	return c;
}



vector<obj> tree;

void build(int v, int l, int r, vector<obj>& a) {
	if (r - l == 1) {
		tree[v] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m, a);
	build(v * 2 + 1, m, r, a);
	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;

	vector<obj> a(N);
	for (int i = 0; i < N; ++i) {
		a[i].x = X[i];
		a[i].mx = X[i];
		a[i].y = Y[i];
		a[i].my = Y[i];
	}
	build(1, 0, N, a);
	return tree[1].y;
}

void upd(int v, int l, int r, int qi, int qx, int qy) {
	if (r - l == 1) {
		if (qx != -1) {
			tree[v].x = qx;
			tree[v].mx = qx;
		}
		if (qy != -1) {
			tree[v].y = qy;
			tree[v].my = qy;
		}
		return;
	}
	int m = (l + r) / 2;
	if (qi < m) upd(v * 2, l, m, qi, qx, qy);
	else upd(v * 2 + 1, m, r, qi, qx, qy);
	tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}

int updateX(int pos, int val) {
	upd(1, 0, n, pos, val, -1);
	return tree[1].y;
}


int updateY(int pos, int val) {
	upd(1, 0, n, pos, -1, val);
	return tree[1].y;
}

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