oj.uz

Submission #158368

# Submission time Handle Problem Language Result Execution time Memory
158368 2019-10-16T19:28:58 Z johutha Horses (IOI15_horses) C++14
17 / 100
 589 ms 79056 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 128 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 252 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 2 ms 376 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 79056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 400 KB Output is correct
16 Correct 2 ms 296 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 252 KB Output is correct
21 Incorrect 2 ms 256 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 392 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Incorrect 2 ms 256 KB Output isn't correct
22 Halted 0 ms 0 KB -