Submission #1291167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291167		kustov_vadim_533	Horses (IOI15_horses)	C++20	34 / 100	1598 ms	22260 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 double ld;

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

const int M = 1e9 + 7;

const int sz = 1 << 20;

int x[sz], rx[sz], mxy[sz];
bool fx[sz];

pair<int, int> a[sz];

void upd(int v, int l, int r) {
	if (r - l == 1) {
		x[v] = a[l].first;
		fx[v] = false;
		rx[v] = -1;
		if (x[v] > 1 || l == 0) {
			rx[v] = l;
		}
		mxy[v] = a[l].second;
	}
	else {
		x[v] = (x[v * 2] * 1ll * x[v * 2 + 1]) % M;
		fx[v] = fx[v * 2] || fx[v * 2 + 1] || (x[v * 2] * 1ll * x[v * 2 + 1] >= M);
		rx[v] = max(rx[v * 2], rx[v * 2 + 1]);
		mxy[v] = max(mxy[v * 2], mxy[v * 2 + 1]);
	}
}

int get_x(int v, int l, int r, int ql, int qr) {
	if (l >= qr || ql >= r) return 1;
	if (l >= ql && r <= qr) return x[v];

	int m = (l + r) / 2;
	int r1 = get_x(v * 2, l, m, ql, qr);
	int r2 = get_x(v * 2 + 1, m, r, ql, qr);
	return (r1 * 1ll * r2) % M;
}
int get_mxy(int v, int l, int r, int ql, int qr) {
	if (l >= qr || ql >= r) return 1;
	if (l >= ql && r <= qr) return mxy[v];

	int m = (l + r) / 2;
	int r1 = get_mxy(v * 2, l, m, ql, qr);
	int r2 = get_mxy(v * 2 + 1, m, r, ql, qr);
	return max(r1, r2);
}
int get_rx(int v, int l, int r, int ql, int qr) {
	if (l >= qr || ql >= r) return -1;
	if (l >= ql && r <= qr) return rx[v];

	int m = (l + r) / 2;
	int r1 = get_rx(v * 2, l, m, ql, qr);
	int r2 = get_rx(v * 2 + 1, m, r, ql, qr);
	return max(r1, r2);
}
bool get_fx(int v, int l, int r, int ql, int qr) {
	if (l >= qr || ql >= r) return false;
	if (l >= ql && r <= qr) return fx[v];

	int m = (l + r) / 2;
	bool r1 = get_fx(v * 2, l, m, ql, qr);
	bool r2 = get_fx(v * 2 + 1, m, r, ql, qr);
	return r1 || r2;
}

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

	int i = n;
	for (int j = 0; j < 40 && i > 0; ++j) {
		i = get_rx(1, 0, n, 0, i);

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

		if (!get_fx(1, 0, n, i + 1, mx + 1) && get_x(1, 0, n, i + 1, mx + 1) * 1ll * get_mxy(1, 0, n, mx, n) < get_mxy(1, 0, n, i, n)) {
			mx = i;
		}
	}
	return (get_x(1, 0, n, 0, mx + 1) * 1ll * get_mxy(1, 0, n, mx, n)) % M;
}

void build(int v, int l, int r) {
	if (r - l == 1) {
		upd(v, l, r);
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	upd(v, l, r);
}

int init(int N, int X[], int Y[]) {
	n = 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) {
		upd(v, l, r);
		return;
	}
	int m = (l + r) / 2;
	if (qi < m) upd(v * 2, l, m, qi);
	else upd(v * 2 + 1, m, r, qi);
	upd(v, l, r);
}

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: 0 / 23
• Subtask 5: 0 / 23