oj.uz

Submission #66207

# Submission time Handle Problem Language Result Execution time Memory
66207 2018-08-10T04:45:34 Z daniel_02 Horses (IOI15_horses) C++17
54 / 100
 645 ms 190192 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 = 5e5 + 7;

ll n, x[sz], y[sz];
pair<double, ll> t[sz * 10], ad[sz * 10], 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);
            ~~~~~~~~~^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 55160 KB Output is correct
2 Correct 40 ms 55272 KB Output is correct
3 Correct 42 ms 55272 KB Output is correct
4 Correct 42 ms 55272 KB Output is correct
5 Correct 41 ms 55272 KB Output is correct
6 Correct 41 ms 55272 KB Output is correct
7 Correct 41 ms 55316 KB Output is correct
8 Correct 42 ms 55316 KB Output is correct
9 Correct 41 ms 55316 KB Output is correct
10 Correct 39 ms 55512 KB Output is correct
11 Correct 42 ms 55512 KB Output is correct
12 Correct 39 ms 55512 KB Output is correct
13 Correct 46 ms 55512 KB Output is correct
14 Correct 42 ms 55512 KB Output is correct
15 Correct 45 ms 55512 KB Output is correct
16 Correct 43 ms 55512 KB Output is correct
17 Correct 46 ms 55512 KB Output is correct
18 Correct 44 ms 55512 KB Output is correct
19 Correct 45 ms 55512 KB Output is correct
20 Correct 45 ms 55512 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55512 KB Output is correct
2 Correct 43 ms 55512 KB Output is correct
3 Correct 41 ms 55512 KB Output is correct
4 Correct 42 ms 55512 KB Output is correct
5 Correct 48 ms 55512 KB Output is correct
6 Correct 44 ms 55512 KB Output is correct
7 Correct 46 ms 55512 KB Output is correct
8 Correct 41 ms 55512 KB Output is correct
9 Correct 40 ms 55520 KB Output is correct
10 Correct 42 ms 55520 KB Output is correct
11 Correct 39 ms 55524 KB Output is correct
12 Correct 48 ms 55524 KB Output is correct
13 Correct 41 ms 55608 KB Output is correct
14 Correct 40 ms 55608 KB Output is correct
15 Correct 44 ms 55608 KB Output is correct
16 Correct 41 ms 55608 KB Output is correct
17 Correct 43 ms 55608 KB Output is correct
18 Correct 50 ms 55608 KB Output is correct
19 Correct 49 ms 55608 KB Output is correct
20 Correct 39 ms 55608 KB Output is correct
21 Correct 40 ms 55608 KB Output is correct
22 Correct 50 ms 55608 KB Output is correct
23 Correct 50 ms 55700 KB Output is correct
24 Correct 46 ms 55720 KB Output is correct
25 Correct 57 ms 55756 KB Output is correct
26 Correct 41 ms 55804 KB Output is correct
27 Correct 44 ms 55832 KB Output is correct
28 Correct 46 ms 55852 KB Output is correct
29 Correct 41 ms 55852 KB Output is correct
30 Correct 44 ms 56004 KB Output is correct
31 Correct 43 ms 56004 KB Output is correct
32 Correct 49 ms 56004 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 96584 KB Output is correct
2 Correct 605 ms 132468 KB Output is correct
3 Correct 546 ms 132568 KB Output is correct
4 Correct 645 ms 132568 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 132568 KB Output is correct
2 Correct 41 ms 132568 KB Output is correct
3 Correct 42 ms 132568 KB Output is correct
4 Correct 43 ms 132568 KB Output is correct
5 Correct 41 ms 132568 KB Output is correct
6 Correct 50 ms 132568 KB Output is correct
7 Correct 49 ms 132568 KB Output is correct
8 Correct 44 ms 132568 KB Output is correct
9 Correct 42 ms 132568 KB Output is correct
10 Correct 49 ms 132568 KB Output is correct
11 Correct 45 ms 132568 KB Output is correct
12 Correct 40 ms 132568 KB Output is correct
13 Correct 42 ms 132568 KB Output is correct
14 Correct 39 ms 132568 KB Output is correct
15 Correct 47 ms 132568 KB Output is correct
16 Correct 47 ms 132568 KB Output is correct
17 Correct 40 ms 132568 KB Output is correct
18 Correct 53 ms 132568 KB Output is correct
19 Correct 47 ms 132568 KB Output is correct
20 Correct 42 ms 132568 KB Output is correct
21 Correct 53 ms 132568 KB Output is correct
22 Correct 44 ms 132568 KB Output is correct
23 Correct 44 ms 132568 KB Output is correct
24 Correct 42 ms 132568 KB Output is correct
25 Correct 45 ms 132568 KB Output is correct
26 Correct 52 ms 132568 KB Output is correct
27 Correct 46 ms 132568 KB Output is correct
28 Correct 43 ms 132568 KB Output is correct
29 Correct 46 ms 132568 KB Output is correct
30 Correct 45 ms 132568 KB Output is correct
31 Correct 48 ms 132568 KB Output is correct
32 Correct 52 ms 132568 KB Output is correct
33 Correct 204 ms 132568 KB Output is correct
34 Correct 213 ms 132568 KB Output is correct
35 Correct 194 ms 132568 KB Output is correct
36 Correct 198 ms 132568 KB Output is correct
37 Correct 145 ms 134504 KB Output is correct
38 Correct 171 ms 134504 KB Output is correct
39 Correct 133 ms 134504 KB Output is correct
40 Correct 169 ms 134504 KB Output is correct
41 Correct 113 ms 134504 KB Output is correct
42 Correct 122 ms 134504 KB Output is correct
43 Incorrect 151 ms 134504 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 134504 KB Output is correct
2 Correct 43 ms 134504 KB Output is correct
3 Correct 43 ms 134504 KB Output is correct
4 Correct 45 ms 134504 KB Output is correct
5 Correct 41 ms 134504 KB Output is correct
6 Correct 41 ms 134504 KB Output is correct
7 Correct 46 ms 134504 KB Output is correct
8 Correct 39 ms 134504 KB Output is correct
9 Correct 42 ms 134504 KB Output is correct
10 Correct 46 ms 134504 KB Output is correct
11 Correct 41 ms 134504 KB Output is correct
12 Correct 47 ms 134504 KB Output is correct
13 Correct 50 ms 134504 KB Output is correct
14 Correct 44 ms 134504 KB Output is correct
15 Correct 43 ms 134504 KB Output is correct
16 Correct 69 ms 134504 KB Output is correct
17 Correct 49 ms 134504 KB Output is correct
18 Correct 41 ms 134504 KB Output is correct
19 Correct 44 ms 134504 KB Output is correct
20 Correct 41 ms 134504 KB Output is correct
21 Correct 46 ms 134504 KB Output is correct
22 Correct 46 ms 134504 KB Output is correct
23 Correct 45 ms 134504 KB Output is correct
24 Correct 44 ms 134504 KB Output is correct
25 Correct 42 ms 134504 KB Output is correct
26 Correct 44 ms 134504 KB Output is correct
27 Correct 44 ms 134504 KB Output is correct
28 Correct 48 ms 134504 KB Output is correct
29 Correct 45 ms 134504 KB Output is correct
30 Correct 51 ms 134504 KB Output is correct
31 Correct 48 ms 134504 KB Output is correct
32 Correct 42 ms 134504 KB Output is correct
33 Correct 224 ms 134504 KB Output is correct
34 Correct 587 ms 156948 KB Output is correct
35 Correct 523 ms 160720 KB Output is correct
36 Correct 616 ms 168388 KB Output is correct
37 Correct 219 ms 168388 KB Output is correct
38 Correct 222 ms 168388 KB Output is correct
39 Correct 223 ms 168388 KB Output is correct
40 Correct 197 ms 169676 KB Output is correct
41 Correct 140 ms 182212 KB Output is correct
42 Correct 163 ms 182212 KB Output is correct
43 Correct 126 ms 182212 KB Output is correct
44 Correct 158 ms 183364 KB Output is correct
45 Correct 136 ms 184976 KB Output is correct
46 Correct 147 ms 186888 KB Output is correct
47 Incorrect 142 ms 190192 KB Output isn't correct
48 Halted 0 ms 0 KB -