oj.uz

Submission #66222

# Submission time Handle Problem Language Result Execution time Memory
66222 2018-08-10T05:05:29 Z daniel_02 Horses (IOI15_horses) C++17
100 / 100
 1046 ms 411620 KB 
#include "horses.h"
#include "bits/stdc++.h"

#define ll long long
#define fr first
#define sc second
#define double long double

using namespace std;

const int MOD = 1e9 + 7;
const int sz = 5e6 + 7;

ll n, x[sz], y[sz];
pair<double, ll> t[sz * 2], ad[sz * 2], 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 * 2 - 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:58:22: warning: unused parameter 'tl' [-Wunused-parameter]
 void push(int v, int tl, int tr)
                      ^~
horses.cpp:58: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:178:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     build(1, 1, n);
                  ^
horses.cpp:180: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:187:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     updx(1, 1, n, pos, n, a, b);
                               ^
horses.cpp:187:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:189: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:198:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     updy(1, 1, n, pos, a, b);
                            ^
horses.cpp:202:21: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (t[1].sc % MOD);
            ~~~~~~~~~^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 313468 KB Output is correct
2 Correct 234 ms 313520 KB Output is correct
3 Correct 249 ms 313520 KB Output is correct
4 Correct 236 ms 313532 KB Output is correct
5 Correct 233 ms 313660 KB Output is correct
6 Correct 231 ms 313660 KB Output is correct
7 Correct 237 ms 313660 KB Output is correct
8 Correct 229 ms 313660 KB Output is correct
9 Correct 220 ms 313708 KB Output is correct
10 Correct 226 ms 313708 KB Output is correct
11 Correct 226 ms 313748 KB Output is correct
12 Correct 220 ms 313748 KB Output is correct
13 Correct 223 ms 313792 KB Output is correct
14 Correct 211 ms 313916 KB Output is correct
15 Correct 214 ms 313916 KB Output is correct
16 Correct 208 ms 313916 KB Output is correct
17 Correct 226 ms 313916 KB Output is correct
18 Correct 227 ms 313916 KB Output is correct
19 Correct 225 ms 313916 KB Output is correct
20 Correct 208 ms 313916 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 313916 KB Output is correct
2 Correct 250 ms 313916 KB Output is correct
3 Correct 242 ms 313916 KB Output is correct
4 Correct 236 ms 313916 KB Output is correct
5 Correct 230 ms 313916 KB Output is correct
6 Correct 225 ms 313916 KB Output is correct
7 Correct 224 ms 313916 KB Output is correct
8 Correct 228 ms 313916 KB Output is correct
9 Correct 257 ms 313916 KB Output is correct
10 Correct 211 ms 313916 KB Output is correct
11 Correct 213 ms 313916 KB Output is correct
12 Correct 225 ms 313916 KB Output is correct
13 Correct 222 ms 313916 KB Output is correct
14 Correct 209 ms 313916 KB Output is correct
15 Correct 226 ms 313916 KB Output is correct
16 Correct 246 ms 313916 KB Output is correct
17 Correct 220 ms 313916 KB Output is correct
18 Correct 212 ms 313916 KB Output is correct
19 Correct 205 ms 313916 KB Output is correct
20 Correct 210 ms 313916 KB Output is correct
21 Correct 219 ms 313916 KB Output is correct
22 Correct 228 ms 313916 KB Output is correct
23 Correct 216 ms 313916 KB Output is correct
24 Correct 224 ms 313916 KB Output is correct
25 Correct 229 ms 313916 KB Output is correct
26 Correct 230 ms 313916 KB Output is correct
27 Correct 238 ms 313920 KB Output is correct
28 Correct 218 ms 313920 KB Output is correct
29 Correct 229 ms 313920 KB Output is correct
30 Correct 228 ms 313940 KB Output is correct
31 Correct 215 ms 313940 KB Output is correct
32 Correct 216 ms 313940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 374988 KB Output is correct
2 Correct 920 ms 407828 KB Output is correct
3 Correct 867 ms 407856 KB Output is correct
4 Correct 1020 ms 407856 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 407856 KB Output is correct
2 Correct 214 ms 407856 KB Output is correct
3 Correct 231 ms 407856 KB Output is correct
4 Correct 270 ms 407856 KB Output is correct
5 Correct 226 ms 407856 KB Output is correct
6 Correct 227 ms 407856 KB Output is correct
7 Correct 224 ms 407856 KB Output is correct
8 Correct 218 ms 407856 KB Output is correct
9 Correct 249 ms 407856 KB Output is correct
10 Correct 231 ms 407856 KB Output is correct
11 Correct 225 ms 407856 KB Output is correct
12 Correct 217 ms 407856 KB Output is correct
13 Correct 221 ms 407856 KB Output is correct
14 Correct 219 ms 407856 KB Output is correct
15 Correct 228 ms 407856 KB Output is correct
16 Correct 221 ms 407856 KB Output is correct
17 Correct 206 ms 407856 KB Output is correct
18 Correct 207 ms 407856 KB Output is correct
19 Correct 206 ms 407856 KB Output is correct
20 Correct 209 ms 407856 KB Output is correct
21 Correct 208 ms 407856 KB Output is correct
22 Correct 223 ms 407856 KB Output is correct
23 Correct 219 ms 407856 KB Output is correct
24 Correct 209 ms 407856 KB Output is correct
25 Correct 223 ms 407856 KB Output is correct
26 Correct 212 ms 407856 KB Output is correct
27 Correct 211 ms 407856 KB Output is correct
28 Correct 227 ms 407856 KB Output is correct
29 Correct 234 ms 407856 KB Output is correct
30 Correct 217 ms 407856 KB Output is correct
31 Correct 213 ms 407856 KB Output is correct
32 Correct 222 ms 407856 KB Output is correct
33 Correct 397 ms 407856 KB Output is correct
34 Correct 427 ms 407856 KB Output is correct
35 Correct 415 ms 407856 KB Output is correct
36 Correct 451 ms 407856 KB Output is correct
37 Correct 367 ms 407856 KB Output is correct
38 Correct 376 ms 407856 KB Output is correct
39 Correct 354 ms 407856 KB Output is correct
40 Correct 385 ms 407856 KB Output is correct
41 Correct 339 ms 407856 KB Output is correct
42 Correct 328 ms 407856 KB Output is correct
43 Correct 384 ms 407856 KB Output is correct
44 Correct 347 ms 407856 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 407856 KB Output is correct
2 Correct 208 ms 407856 KB Output is correct
3 Correct 225 ms 407856 KB Output is correct
4 Correct 216 ms 407856 KB Output is correct
5 Correct 215 ms 407856 KB Output is correct
6 Correct 208 ms 407856 KB Output is correct
7 Correct 223 ms 407856 KB Output is correct
8 Correct 235 ms 407856 KB Output is correct
9 Correct 235 ms 407856 KB Output is correct
10 Correct 232 ms 407856 KB Output is correct
11 Correct 229 ms 407856 KB Output is correct
12 Correct 208 ms 407856 KB Output is correct
13 Correct 232 ms 407856 KB Output is correct
14 Correct 229 ms 407856 KB Output is correct
15 Correct 227 ms 407856 KB Output is correct
16 Correct 226 ms 407856 KB Output is correct
17 Correct 225 ms 407856 KB Output is correct
18 Correct 221 ms 407856 KB Output is correct
19 Correct 210 ms 407856 KB Output is correct
20 Correct 240 ms 407856 KB Output is correct
21 Correct 234 ms 407856 KB Output is correct
22 Correct 212 ms 407856 KB Output is correct
23 Correct 211 ms 407856 KB Output is correct
24 Correct 222 ms 407856 KB Output is correct
25 Correct 207 ms 407856 KB Output is correct
26 Correct 215 ms 407856 KB Output is correct
27 Correct 231 ms 407856 KB Output is correct
28 Correct 239 ms 407856 KB Output is correct
29 Correct 215 ms 407856 KB Output is correct
30 Correct 215 ms 407856 KB Output is correct
31 Correct 236 ms 407856 KB Output is correct
32 Correct 209 ms 407856 KB Output is correct
33 Correct 429 ms 407856 KB Output is correct
34 Correct 990 ms 407876 KB Output is correct
35 Correct 937 ms 407876 KB Output is correct
36 Correct 1046 ms 407876 KB Output is correct
37 Correct 418 ms 407876 KB Output is correct
38 Correct 434 ms 407876 KB Output is correct
39 Correct 412 ms 407876 KB Output is correct
40 Correct 423 ms 407876 KB Output is correct
41 Correct 337 ms 407876 KB Output is correct
42 Correct 371 ms 407876 KB Output is correct
43 Correct 334 ms 407876 KB Output is correct
44 Correct 365 ms 407876 KB Output is correct
45 Correct 335 ms 407876 KB Output is correct
46 Correct 347 ms 407876 KB Output is correct
47 Correct 370 ms 407876 KB Output is correct
48 Correct 362 ms 407876 KB Output is correct
49 Correct 899 ms 411620 KB Output is correct
50 Correct 899 ms 411620 KB Output is correct
51 Correct 551 ms 411620 KB Output is correct
52 Correct 586 ms 411620 KB Output is correct
53 Correct 659 ms 411620 KB Output is correct
54 Correct 682 ms 411620 KB Output is correct
55 Correct 637 ms 411620 KB Output is correct
56 Correct 667 ms 411620 KB Output is correct
57 Correct 432 ms 411620 KB Output is correct
58 Correct 470 ms 411620 KB Output is correct
59 Correct 330 ms 411620 KB Output is correct