Submission #1000305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000305		jer033	Horses (IOI15_horses)	C++17	0 / 100	1543 ms	15272 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;
	if ((j<30) and ((j==0) or ((candidates[j-1]!=0))))
	{
		newcandidates.push_back(0);
		mybes.push_back(rangequery(0, candidates[j-1]-1));
	}
	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();
	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]]);
			currmul = 1;
			bes = mybes[i];
		}
		else
		{
			currmul = boundmul(currmul, x[candidates[i]]);
		}
	}
	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:148:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  148 |  int m = candidates.size();
      |          ~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:178:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  178 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:185:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  185 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:209:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  209 |  return solve();
      |         ~~~~~^~

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