Submission #417177

#	Time	Username	Problem	Language	Result	Execution time	Memory
417177		Jasiekstrz	Horses (IOI15_horses)	C++17	100 / 100	384 ms	49160 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"
#define fi first
#define se second
using namespace std;
const int NN=5e5;
const int PP=53e4;
const long long MOD=1e9+7;
struct Frac
{
	long long a,b;
	bool operator<(const Frac &oth) const
	{
		return a*oth.b<oth.a*b;
	}
};
int n;
int pot;
long long prod;
int tree[2*PP+10];
int x[NN+10];
int y[NN+10];
set<int> st;
long long qp(int a,int b)
{
	if(b==0)
		return 1;
	long long tmp=qp(a,b/2);
	tmp=(tmp*tmp)%MOD;
	if(b%2==1)
		return (tmp*a)%MOD;
	return tmp;
}
void add_t(int g,int c)
{
	g+=pot-1;
	tree[g]=c;
	for(g/=2;g>=1;g/=2)
		tree[g]=max(tree[2*g],tree[2*g+1]);
	return;
}
int read_t(int l,int r)
{
	int ans=0;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans=max(ans,tree[l++]);
		if(r%2==0)
			ans=max(ans,tree[r--]);
	}
	return ans;
}
int get_ans()
{
	Frac w={y[n],1};
	long long den=1;
	for(auto it=prev(st.end());true;it--)
	{
		den*=x[*it];
		if(den>=MOD)
			break;
		if(it==st.begin())
		{
			Frac tmp={read_t(1,(*it)-1),den};
			w=max(w,tmp);
			break;
		}
		Frac tmp={read_t(*prev(it),(*it)-1),den};
		w=max(w,tmp);
	}
	//cerr<<prod<<" "<<w.a<<" "<<w.b<<"\n";
	return (((prod*w.a)%MOD)*qp(w.b,MOD-2))%MOD;
}
int init(int N,int X[],int Y[])
{
	n=N;
	for(int i=0;i<n;i++)
	{
		x[i+1]=X[i];
		y[i+1]=Y[i];
	}
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=n;i++)
		tree[pot+i-1]=y[i];
	for(int i=pot-1;i>=1;i--)
		tree[i]=max(tree[2*i],tree[2*i+1]);
	prod=1;
	for(int i=1;i<=n;i++)
	{
		prod*=x[i];
		prod%=MOD;
		if(x[i]>1 || i==n)
			st.insert(i);
	}
	return get_ans();
}
int updateX(int pos,int val)
{
	prod=(prod*qp(x[pos+1],MOD-2))%MOD;
	prod=(prod*val)%MOD;
	x[pos+1]=val;
	st.erase(pos+1);
	if(val>1 || pos+1==n)
		st.insert(pos+1);
	return get_ans();
}
int updateY(int pos,int val)
{
	y[pos+1]=val;
	add_t(pos+1,val);
	return get_ans();
}

Compilation message (stderr)

horses.cpp: In function 'int get_ans()':
horses.cpp:73:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |  return (((prod*w.a)%MOD)*qp(w.b,MOD-2))%MOD;
      |                              ~~^
horses.cpp:73:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |  return (((prod*w.a)%MOD)*qp(w.b,MOD-2))%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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