Submission #1291150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291150		kustov_vadim_533	Horses (IOI15_horses)	C++20	57 / 100	1600 ms	102456 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;
	ld dx = 1;

	int rx = -1;
	int mxy = 1;

	obj() = default;
	obj(int x_, int y_, int i) {
		x = x_;
		dx = x_;
		if (x_ > 1 || i == 0) {
			rx = i;
		}
		mxy = y_;
	}
};


obj merge(obj a, obj b) {
	obj c;
	c.x = (a.x * 1ll * b.x) % M;
	c.dx = a.dx * b.dx;
	c.rx = max(a.rx, b.rx);
	c.mxy = max(a.mxy, b.mxy);
	return c;
}


vector<pair<int, int>> a;
vector<obj> tree;

obj get(int v, int l, int r, int ql, int qr) {
	if (l >= qr || ql >= r) return obj();
	if (l >= ql && r <= qr) return tree[v];

	int m = (l + r) / 2;
	obj r1 = get(v * 2, l, m, ql, qr);
	obj r2 = get(v * 2 + 1, m, r, ql, qr);
	return merge(r1, r2);
}

int n;
int solve() {
	int mx = n - 1;

	int r = n;
	while (get(1, 0, n, r, n).dx <= 2e9 && r > 0) {
		int i = get(1, 0, n, 0, r).rx;
		r = i;

		if (i == -1) {
			break;
		}

		if (get(1, 0, n, i + 1, mx + 1).dx * get(1, 0, n, mx, n).mxy < get(1, 0, n, i, n).mxy) {
			mx = i;
		}
	}
	return (get(1, 0, n, 0, mx + 1).x * 1ll * get(1, 0, n, mx, n).mxy) % M;
}

void build(int v, int l, int r) {
	if (r - l == 1) {
		tree[v] = obj(a[l].first, a[l].second, 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 init(int N, int X[], int Y[]) {
	tree.resize(4 * N);
	n = N;

	a.resize(N);

	for (int i = 0; i < N; ++i) {
		a[i].first = X[i];
		a[i].second = Y[i];
	}
	build(1, 0, N);
	return solve();
}

void upd(int v, int l, int r, int qi) {
	if (r - l == 1) {
		tree[v] = obj(a[l].first, a[l].second, 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) {
	a[pos].first = val;
	upd(1, 0, n, pos);
	return solve();
}


int updateY(int pos, int val) {
	a[pos].second = val;
	upd(1, 0, n, pos);
	return solve();
}

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