Submission #1000284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000284		jer033	Horses (IOI15_horses)	C++17	0 / 100	1587 ms	15296 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MOD = 1'000'000'007;
const ll INF = 1'000'000'006;
const int pus = 524288;

ll regmul(ll a, ll b)
{
	return (a*b)%MOD;
}

ll boundmul(ll a, ll b)
{
	return min(INF, a*b);
}

ll modpow(ll x, int y)
{
	if (y==0)
		return 1;
	if (y==1)
		return x;
	ll z = modpow(x, y/2);
	z = regmul(z, z);
	if (y%2)
		z = regmul(z, x);
	return z;
}

ll modinv(ll a, ll b)
{
	return regmul(a, modpow(b, MOD-2));
}

vector<int> x;
vector<int> y;
int n;

int segtree[1048576];

void setupsegtree()
{
	for (int i=0; i<n; i++)
	{
		segtree[pus+i] = y[i];
	}
	for (int i=pus-1; i>=1; i--)
	{
		segtree[i] = max(segtree[2*i], segtree[2*i+1]);
	}
}

void updatesegtree(int index, int newval)
{
	index = pus+index;
	segtree[index] = newval;
	while (index!=0)
	{
		index = index/2;
		segtree[index] = max(segtree[2*index], segtree[2*index+1]);
	}
	segtree[0] = 0;
}

int rangequery(int indexa, int indexb)
{
	indexa = indexa+pus;
	indexb = indexb+pus;
	int ans = -1;
	while ((indexb-indexa)>=5)
	{
		if ((indexa%2)==1)
		{
			ans = max(segtree[indexa], ans);
			indexa++;
		}
		if ((indexb%2)==0)
		{
			ans = max(segtree[indexb], ans);
			indexb--;
		}
		indexa = indexa/2;
		indexb = indexb/2;
	}
	for (int i=indexa; i<=indexb; i++)
		ans = max(segtree[i], ans);
	return ans;
}

priority_queue<int> nonone;
vector<int> candidates;
vector<int> mybes;
ll c;

void initpq()
{
	while (not nonone.empty())
		nonone.pop();
	candidates.clear();
	mybes.clear();
	c = 1;
	for (int i=0; i<n; i++)
	{
		if (x[i]>1)
		{
			nonone.push(i);
			c = regmul(c, x[i]);
		}
	}
	int j = 0;
	while ((j<30) and (not nonone.empty()))
	{
		candidates.push_back(nonone.top());
		c = modinv(c, x[nonone.top()]);
		nonone.pop();
		j++;
	}
	//reverse the list
	vector<int> newcandidates;
	for (int i=j-1; i>=0; i--)
	{
		newcandidates.push_back(candidates[i]);
	}
	candidates = newcandidates;

	for (int i=0; i<j; i++)
	{
		if (i!=(j-1))
		{
			mybes.push_back(rangequery(candidates[i], candidates[i+1]-1));
		}
		else
		{
			mybes.push_back(rangequery(candidates[i], n-1));
		}
	}
}

ll solve()
{
	int m = candidates.size();
	if (m==0)
		return rangequery(0, n-1);
	ll isans = 1;
	ll safe = x[candidates[0]];
	ll bes = mybes[0];
	ll currmul = 1;
	for (int i=1; i<m; i++)
	{
		if (boundmul(boundmul(currmul, x[candidates[i]]), mybes[i])>=bes)
		{
			safe = regmul(safe, currmul);
			safe = regmul(safe, x[candidates[i]]);
			isans = boundmul(safe, currmul);
			isans = boundmul(safe, x[candidates[i]]);
			currmul = 1;
			bes = mybes[i];
		}
		else
		{
			currmul = regmul(currmul, x[candidates[i]]);
		}
	}
	isans = boundmul(isans, bes);
	isans = boundmul(isans, c);
	ll secans = rangequery(0, candidates[0]-1);
	if (candidates[0]>0)
	{
		ll secans = rangequery(0, candidates[0]-1);
		if (secans>isans)
			return secans;
	}
	return regmul(c, regmul(safe, bes));
}

int init(int N, int X[], int Y[]) {
	for (int i=0; i<N; i++)
	{
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	n=N;
	setupsegtree();
    initpq();
	return solve();
}

int updateX(int pos, int val) {	
	x[pos] = val;
	setupsegtree();
	initpq();
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	setupsegtree();
	initpq();
	/*
	updatesegtree(pos, val);
	int j = candidates.size();
	for (int i=0; i<j; i++)
	{
		if (i!=(j-1))
		{
			if ((candidates[i]<=pos) and (pos<candidates[i+1]))
				mybes[i] = rangequery(candidates[i], candidates[i+1]-1);
		}
		else
		{
			if (candidates[i]<=pos)
				mybes[i] = rangequery(candidates[i], n-1);
		}
	}*/

	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'll solve()':
horses.cpp:143:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  143 |  int m = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp:171:6: warning: declaration of 'secans' shadows a previous local [-Wshadow]
  171 |   ll secans = rangequery(0, candidates[0]-1);
      |      ^~~~~~
horses.cpp:168:5: note: shadowed declaration is here
  168 |  ll secans = rangequery(0, candidates[0]-1);
      |     ^~~~~~
horses.cpp:168:5: warning: unused variable 'secans' [-Wunused-variable]
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:187:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  187 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:194:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  194 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:218:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  218 |  return solve();
      |         ~~~~~^~

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