Submission #292346

#	Time	Username	Problem	Language	Result	Execution time	Memory
292346		VodkaInTheJar	Horses (IOI15_horses)	C++14	100 / 100	907 ms	53496 KiB

horses

#include <bits/stdc++.h>
 
using namespace std;

const int maxn = 5e5 + 3; 
const int mod = 1e9 + 7; 

int n, x[maxn], y[maxn];
set <int> s;

pair <int, int> tr[maxn * 4];
void merge(int v)
{
	tr[v].first = max(tr[v * 2].first, tr[v * 2 + 1].first);
	tr[v].second = 1ll * tr[v * 2].second * tr[v * 2 + 1].second % mod;
}

void build(int v, int l, int r)
{
	if (l == r)
	{
		tr[v] = {y[l], x[l]};
		return;
	}
	
	int mid = (l + r) / 2;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	
	merge(v);
}

int get1(int v, int l, int r, int ll, int rr)
{
	if (l > rr || r < ll)
	return -1;
	
	if (l >= ll && r <= rr)
	return tr[v].first;
	
	int mid = (l + r) / 2;
	return max(get1(v * 2, l, mid, ll, rr), get1(v * 2 + 1, mid + 1, r, ll, rr));
}

int get2(int v, int l, int r, int ll, int rr)
{
	if (l > rr || r < ll)
	return 1;
	
	if (l >= ll && r <= rr)
	return tr[v].second;
	
	int mid = (l + r) / 2;
	return 1ll * get2(v * 2, l, mid, ll, rr) * get2(v * 2 + 1, mid + 1, r, ll, rr) % mod;
}

void update1(int v, int l, int r, int pos, int val)
{
	if (l == r)
	{
		tr[v].first = val;
		return;
	}
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	update1(v * 2, l, mid, pos, val);
	
	else
	update1(v * 2 + 1, mid + 1, r, pos, val);
	
	merge(v);
}

void update2(int v, int l, int r, int pos, int val)
{
	if (l == r)
	{
		tr[v].second = val;
		return;
	}
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	update2(v * 2, l, mid, pos, val);
	
	else
	update2(v * 2 + 1, mid + 1, r, pos, val);
	
	merge(v);
}

int get()
{
	if (s.empty())
	return get1(1, 1, n, 1, n);
	
	else 
	{
		long long pr = 1; 
		auto it = prev(s.end());
		
		while (it != s.begin() && pr <= 1000000000)
		{
			pr *= x[*it];
			it--;
		}
		
		if (it != s.begin() || pr >= 1000000000)
		it++;
		
		int to_mult = get2(1, 1, n, 1, *it);
		auto it1 = it;
		
		pr = 1; 
		long long ans = -1;
		while (it != s.end())
		{
			ans = max(ans, pr * y[*it]);
			
			int l = *it + 1, r;
			if (it != prev(s.end()))
			r = *next(it) - 1;
			
			else 
			r = n; 
			
			if (l <= r) 
				ans = max(ans, pr * get1(1, 1, n, l, r));
			
			it++;
			if (it != s.end())
			pr *= x[*it];
		}
		
		if (it1 == s.begin() && *it1 != 1)
		{
			if (pr * x[*it1] <= 1000000000)
			{
				auto curr = get1(1, 1, n, 1, *it1 - 1);
				if (curr / x[*it1] >= ans)
				return curr; 
			}
		}
		
		return 1ll * (ans % mod) * to_mult % 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];
	
	build(1, 1, n);
	for (int i = 1; i <= n; i++)
	if (x[i] != 1)
	s.insert(i);
	
	return get();
}

int updateX(int pos, int val)
{
	pos++;
	
	if (x[pos] == val)
	return get();
	 
	update2(1, 1, n, pos, val); 
	
	if (val == 1)
	s.erase(pos);
	
	else 
	if (x[pos] == 1)
	s.insert(pos);
	
	x[pos] = val;
	
	return get();
}

int updateY(int pos, int val)
{
	pos++;
	
	y[pos] = val; 
	update1(1, 1, n, pos, val);
	
	return get();
}

/*
int n2, q, x2[maxn], y2[maxn]; 
int main()
{
	cin >> n2;
	for (int i = 0; i < n2; i++)
	cin >> x2[i];
	
	for (int i = 0; i < n2; i++)
	cin >> y2[i];
	 
	cout << init(n2, x2, y2) << endl;

	cin >> q;
	while (q--)
	{
		int type, pos, val;
		cin >> type >> pos >> val;
		
		if (type == 1)
		cout << updateX(pos, val) << endl;
		
		else 
		cout << updateY(pos, val) << endl;
	}
}
*/

Compilation message (stderr)

horses.cpp: In function 'void merge(int)':
horses.cpp:15:63: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 |  tr[v].second = 1ll * tr[v * 2].second * tr[v * 2 + 1].second % mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get2(int, int, int, int, int)':
horses.cpp:54:81: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   54 |  return 1ll * get2(v * 2, l, mid, ll, rr) * get2(v * 2 + 1, mid + 1, r, ll, rr) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get()':
horses.cpp:146:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  146 |   return 1ll * (ans % mod) * to_mult % mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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