oj.uz

Submission #785171

# Submission time Handle Problem Language Result Execution time Memory
785171 2023-07-17T06:46:59 Z Sohsoh84 Horses (IOI15_horses) C++17
34 / 100
 164 ms 44340 KB 
#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 = 1e6 + 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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 340 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 44340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 372 KB Output is correct
33 Incorrect 34 ms 20044 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Incorrect 163 ms 44248 KB Output isn't correct
34 Halted 0 ms 0 KB -