Submission #795162

#	Time	Username	Problem	Language	Result	Execution time	Memory
795162		iee	Horses (IOI15_horses)	C++17	0 / 100	138 ms	94224 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5, P = 1e9 + 7;
using ld = long double;
struct info {
	ld lo;
	int mo;
	explicit info() = default;
	info(ld _lo, int _mo) : lo(_lo), mo(_mo) {
	}
	friend info operator *(const info &p, const info &q) {
		return {p.lo + q.lo, (int) (1LL * p.mo * q.mo % P)};
	}
	friend bool operator <(const info &p, const info &q) {
		return pair{p.lo, p.mo} < pair{q.lo, q.mo};
	}
} tr[N << 2], I{log(1), 1}, lazy[N << 2], ini[N];
vector<int> X, Y;
int n;
int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1LL * res * a % P;
		a = 1LL * a * a % P;
		b /= 2;
	}
	return res;
}
void build(int u, int l, int r) {
	lazy[u] = I;
	if (l == r) {
		tr[u] = ini[l];
		return;
	}
	const int mid = (l + r) >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
void spread(int u) {
	info &ta = lazy[u];
	tr[u << 1] = tr[u << 1] * ta, lazy[u << 1] = lazy[u << 1] * ta;
	tr[u << 1 | 1] = tr[u << 1 | 1] * ta, lazy[u << 1 | 1] = lazy[u << 1 | 1] * ta;
	ta = I;
}
void mul(int u, int ql, int qr, int l, int r, info val) {
	if (l >= ql && r <= qr) {
		lazy[u] = lazy[u] * val;
		tr[u] = tr[u] * val;
		return;
	}
	spread(u);
	const int mid = (l + r) >> 1;
	if (ql <= mid) mul(u << 1, ql, qr, l, mid, val);
	if (qr > mid) mul(u << 1 | 1, ql, qr, mid + 1, r, val);
	tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
int init(int N, int XX[], int YY[]) {
	n = N, X = vector(XX, XX + n), Y = vector(YY, YY + n);
	for (int i = 0; i < n; i++) {
		ini[i].lo = log(X[i]);
		if (i) ini[i].lo += ini[i - 1].lo;
	}
	for (int i = 0; i < n; i++) {
		ini[i].lo += log(Y[i]);
	}
	for (int i = 0; i < n; i++) {
		ini[i].mo = X[i];
		if (i) ini[i].mo = 1LL * ini[i - 1].mo % P;
	}
	for (int i = 0; i < n; i++) {
		ini[i].mo = 1LL * ini[i].mo * Y[i] % P;
	}
	build(1, 0, n - 1);
	return tr[1].mo;
}

int updateX(int pos, int val) {
	info mu{log(val) - log(X[pos]), (int) (1LL * val * qpow(X[pos], P - 2) % P)};
	X[pos] = val;
	mul(1, pos, n - 1, 0, n - 1, mu);
	return tr[1].mo;
}

int updateY(int pos, int val) {
	info mu{log(val) - log(Y[pos]), (int) (1LL * val * qpow(Y[pos], P - 2) % P)};
	Y[pos] = val;
	mul(1, pos, pos, 0, n - 1, mu);
	return tr[1].mo;
}

Compilation message (stderr)

horses.cpp: In function 'int qpow(int, int)':
horses.cpp:24:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   24 |   if (b & 1) res = 1LL * res * a % P;
      |                    ~~~~~~~~~~~~~~^~~
horses.cpp:25:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   25 |   a = 1LL * a * a % P;
      |       ~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:58:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   58 | int init(int N, int XX[], int YY[]) {
      |          ~~~~^
horses.cpp:4:15: note: shadowed declaration is here
    4 | constexpr int N = 5e5 + 5, P = 1e9 + 7;
      |               ^
horses.cpp:72:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   ini[i].mo = 1LL * ini[i].mo * Y[i] % P;
      |               ~~~~~~~~~~~~~~~~~~~~~~~^~~

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