| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66210 |
2018-08-10T04:51:20 Z |
daniel_02 |
Horses (IOI15_horses) |
C++17 |
|
787 ms |
525312 KB |
#include "horses.h"
#include "bits/stdc++.h"
#define ll long long
#define fr first
#define sc second
using namespace std;
const int MOD = 1e9 + 7;
const int sz = 5e6 + 7;
ll n, x[sz], y[sz];
pair<double, ll> t[sz * 7], ad[sz * 7], an[sz];
pair<double, ll> maxp(pair<double, ll> a, pair<double, ll> b)
{
if (a.fr > b.fr)
{
return a;
}
else
{
return b;
}
}
ll bin_pow(ll a, ll k)
{
if (k == 1)return a;
if (k & 1)
return ((a * 1LL * bin_pow(a, k - 1)) % MOD);
else
{
ll b = bin_pow(a, k / 2);
return ((b * b) % MOD);
}
}
void build(int v, int tl, int tr)
{
if (tl == tr)
{
t[v].fr = an[tl].fr;
t[v].sc = an[tl].sc;
}
else
{
int mid = (tl + tr) >> 1;
build(v + v, tl, mid);
build(v + v + 1, mid + 1, tr);
t[v] = maxp(t[v + v], t[v + v + 1]);
}
}
void push(int v, int tl, int tr)
{
if (ad[v].sc == -1)return;
t[v].fr += ad[v].fr;
t[v].sc = (ad[v].sc * t[v].sc) % MOD;
ad[v + v].fr += ad[v].fr;
ad[v + v + 1].fr += ad[v].fr;
if (ad[v + v].sc == -1)ad[v + v].sc = 1;
if (ad[v + v + 1].sc == -1)ad[v + v + 1].sc = 1;
ad[v + v].sc = (ad[v].sc * ad[v + v].sc) % MOD;
ad[v + v + 1].sc = (ad[v].sc * ad[v + v + 1].sc) % MOD;
if (t[v].sc < -1)
t[v].sc *= -1;
ad[v].fr = 0;
ad[v].sc = -1;
}
void updy(int v, int tl, int tr, int pos, double val, ll val1)
{
push(v, tl, tr);
push(v + v, tl, tr);
push(v + v + 1, tl, tr);
if (t[v].sc < -1)
t[v].sc *= -1;
if (tl == tr)
{
t[v].fr += val;
t[v].sc = (t[v].sc * val1) % MOD;
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
updy(v + v, tl, mid, pos, val, val1);
else
updy(v + v + 1, mid + 1, tr, pos, val, val1);
push(v, tl, tr);
push(v + v, tl, tr);
push(v + v + 1, tl, tr);
t[v] = maxp(t[v + v], t[v + v + 1]);
}
}
void updx(int v, int tl, int tr, int l, int r, double val, ll val1)
{
push(v, tl, tr);
push(v + v, tl, tr);
push(v + v + 1, tl, tr);
if (t[v].sc < -1)
t[v].sc *= -1;
if (tl > r || l > tr)return;
if (l <= tl && tr <= r)
{
ad[v].fr += val;
if (ad[v].sc == -1)ad[v].sc = 1;
ad[v].sc = (val1 * 1LL * ad[v].sc) % MOD;
push(v, tl, tr);
push(v + v, tl, tr);
push(v + v + 1, tl, tr);
}
else
{
int mid = (tl + tr) >> 1;
updx(v + v, tl, mid, l, r, val, val1);
updx(v + v + 1, mid + 1, tr, l, r, val, val1);
push(v, tl, tr);
push(v + v, tl, tr);
push(v + v + 1, tl, tr);
t[v] = maxp(t[v + v], t[v + v + 1]);
}
}
int init(int N, int X[], int Y[]) {
double h = 0;
ll cur = 1;
double ans = 0;
ll ans1 = 1;
n = N;
for (int i = 0; i < sz * 7 - 1; i++)
{
ad[i].sc = -1;
}
for (int i = 0; i < N; i++)
{
x[i + 1] = X[i];
y[i + 1] = Y[i];
}
for (int i = 0; i < N; i++)
{
h += log10(X[i]);
cur = (cur * 1LL * X[i]) % MOD;
an[i + 1] = {h + log10(Y[i]), (cur * 1LL * Y[i]) % MOD};
if (ans * 1.0 < h + log10(Y[i]))
{
ans = log10(Y[i]) + h;
ans1 = (Y[i] * 1LL * cur) % MOD;
}
}
build(1, 1, n);
return (ans1 % MOD);
}
int updateX(int pos, int val) {
pos++;
double a = (log10(val) - log10(x[pos]));
ll b = (val * 1LL * bin_pow(x[pos], MOD - 2)) % MOD;
updx(1, 1, n, pos, n, a, b);
x[pos] = val;
return (t[1].sc % MOD);
}
int updateY(int pos, int val) {
pos++;
double a = (log10(val) - log10(y[pos]));
ll b = (val * 1LL * bin_pow(y[pos], MOD - 2)) % MOD;
updy(1, 1, n, pos, a, b);
y[pos] = val;
return (t[1].sc % MOD);
}
Compilation message
horses.cpp: In function 'void push(int, int, int)':
horses.cpp:57:22: warning: unused parameter 'tl' [-Wunused-parameter]
void push(int v, int tl, int tr)
^~
horses.cpp:57:30: warning: unused parameter 'tr' [-Wunused-parameter]
void push(int v, int tl, int tr)
^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:177:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
build(1, 1, n);
^
horses.cpp:179:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (ans1 % MOD);
~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:186:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
updx(1, 1, n, pos, n, a, b);
^
horses.cpp:186:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:188:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (t[1].sc % MOD);
~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:197:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
updy(1, 1, n, pos, a, b);
^
horses.cpp:201:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (t[1].sc % MOD);
~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
787 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
454 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
768 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
475 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
446 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
