Submission #785172

#	Time	Username	Problem	Language	Result	Execution time	Memory
785172		Sohsoh84	Horses (IOI15_horses)	C++17	100 / 100	448 ms	44784 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

#define sep			' '
#define debug(x)		cerr << #x << ": " << x << endl;
#define X			first
#define Y			second

typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 3e6 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
const ll LOG = 30;

inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		b >>= 1;
		a = a * a % MOD;
	}

	return ans;
}

inline bool cmp(pll a, pll b) {
	return a.X * b.Y > a.Y * b.X;
}

ll X[MAXN], Y[MAXN], n;

namespace segment {
	ll sg[MAXN];
	void build(int l = 1, int r = n, int v = 1) {
		if (l == r) sg[v] = Y[l];
		else {
			int mid = (l + r) >> 1;
			build(l, mid, v << 1);
			build(mid + 1, r, v << 1 | 1);
			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	void update(int ind, int l = 1, int r = n, int v = 1) {
		if (l == r) sg[v] = Y[l];
		else {
			int mid = (l + r) >> 1;
			if (ind <= mid) update(ind, l, mid, v << 1);
			else update(ind, mid + 1, r, v << 1 | 1);

			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}

	ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
		if (ql > r || qr < l) return 0;
		if (ql <= l && qr >= r) return sg[v];

		int mid = (l + r) >> 1;
		return max(query(ql, qr, l, mid, v << 1),
				 query(ql, qr, mid + 1, r, v << 1 | 1));
	}
}

set<int> st;
ll mul = 1;

inline ll solve() {
	ll f = 1;
	pll best = {Y[n], 1};

	int j = 0;
	for (auto it = prev(prev(st.end())); j < LOG && f < INF; it--, j++) {
		int nxt = *next(it);
		int i = *it;

		ll mx = segment::query(i, nxt - 1);
		if (cmp(pll(mx, f), best)) best = pll(mx, f);
		f *= X[i];

		if (it == st.begin()) break;
	}

	return mul * best.X % MOD * poww(best.Y, MOD - 2) % MOD;
}

int init(int N_, int X_[], int Y_[]) {
	n = N_;
	for (int i = 1; i <= n; i++) {
		X[i] = X_[i - 1], Y[i] = Y_[i - 1];
		if (X[i] > 1) st.insert(i);
		mul = mul * X[i] % MOD;
	}

	segment::build();
	st.insert(1);
	st.insert(n + 1);
	return solve();
}

int updateX(int pos, int val) {
	pos++;
	mul = mul * poww(X[pos], MOD - 2) % MOD;

	if (pos > 1) {
		if (X[pos] > 1 && val == 1) st.erase(pos);
		else if (X[pos] == 1 && val > 1) st.insert(pos);
	}

	X[pos] = val;
	mul = mul * X[pos] % MOD;
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	Y[pos] = val;
	segment::update(pos);
	return solve();
}

Compilation message (stderr)

horses.cpp:38:44: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   38 |  void build(int l = 1, int r = n, int v = 1) {
      |                                            ^
horses.cpp:48:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |  void update(int ind, int l = 1, int r = n, int v = 1) {
      |                                                      ^
horses.cpp:59:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 |  ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
      |                                                          ^
horses.cpp: In function 'll solve()':
horses.cpp:81:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |   ll mx = segment::query(i, nxt - 1);
      |                                    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   99 |  segment::build();
      |                 ^
horses.cpp:101:14: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
  101 |  st.insert(n + 1);
      |            ~~^~~
horses.cpp:102:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  102 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:116:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |  segment::update(pos);
      |                     ^
horses.cpp:123:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |  return solve();
      |         ~~~~~^~

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