Submission #158368

#	Time	Username	Problem	Language	Result	Execution time	Memory
158368		johutha	Horses (IOI15_horses)	C++14	17 / 100	589 ms	79056 KiB

horses

#include "horses.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

#define double long double
#define int long long
const int MOD = 1e9+7;

using namespace std;

struct segtree
{
	vector<double> table;
	vector<double> op;
	int n;

	void apply(double val, int pos)
	{
		op[pos] += val;
		table[pos] += val;
	}

	void propagate(int pos)
	{
		apply(op[pos], 2*pos + 1);
		apply(op[pos], 2*pos + 2);
		op[pos] = 0;
	}

	void update(int ql, int qr, double v, int l, int r, int pos)
	{
		if (ql <= l && r <= qr)
		{
			apply(v, pos);
			return;
		}
		if (qr < l || r < ql) return;
		propagate(pos);
		update(ql, qr, v, l, (l + r)/2, 2*pos + 1);
		update(ql, qr, v, (l + r)/2 + 1, r, 2*pos + 2);
		table[pos] = max(table[2*pos + 1], table[2*pos + 2]);
	}

	void update(int ql, int qr, double v)
	{
		update(ql, qr, v, 0, n - 1, 0);
	}

	double query(int ql, int qr, int l, int r, int pos)
	{
		if (ql <= l && r <= qr) return table[pos];
		if (qr < l || r < ql) return 0;
		propagate(pos);
		return max(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
	}


	double query(int ql, int qr)
	{
		return query(ql, qr, 0, n - 1, 0);
	}
	
	void init(int in)
	{
		n = in;
		table.resize(4*n, 0);
		op.resize(4*n, 0);
	}
};

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

signed fpm(double d)
{
	int fl = floor(d);
	int ires = 1;
	int c = 1;
	int cr = 2;
	for (int i = 0; i <= ceil(log2(fl)); i++)
	{
		if (c & fl)
		{
			ires *= cr;
		}
		cr *= cr;
		c <<= 1;
		ires %= MOD;
	}
	double res = (double)ires;
	res *= pow(2, d - floor(d));
	int r = round(res);
	return r % MOD;
}

signed init(signed N, signed X[], signed Y[])
{
	n = N;
	st.init(N);
	double curr = 0;
	for (int i = 0; i < N; i++)
	{
		x.push_back(X[i]);
		y.push_back(Y[i]);
		curr += log2(X[i]);
		st.update(i, i, curr + log2(Y[i]));
	}
	double d = st.query(0, n - 1);
	return fpm(d);
}

signed updateX(signed pos, signed val)
{
	double diff = log2(val) - log2(x[pos]);
	st.update(pos, n - 1, diff);
	x[pos] = val;
	return fpm(st.query(0, n - 1));
}

signed updateY(signed pos, signed val)
{
	double diff = log2(val) - log2(y[pos]);
	st.update(pos, pos, diff);
	y[pos] = val;
	return fpm(st.query(0, n - 1));
}

Compilation message (stderr)

horses.cpp: In function 'int fpm(long double)':
horses.cpp:80:16: warning: conversion to 'long long int' from 'long double' may alter its value [-Wfloat-conversion]
  int fl = floor(d);
           ~~~~~^~~
horses.cpp:84:36: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  for (int i = 0; i <= ceil(log2(fl)); i++)
                                    ^
horses.cpp:96:15: warning: conversion to 'long long int' from 'long double' may alter its value [-Wfloat-conversion]
  int r = round(res);
          ~~~~~^~~~~
horses.cpp:97:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return r % MOD;
         ~~^~~~~

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