oj.uz

Submission #64802

# Submission time Handle Problem Language Result Execution time Memory
64802 2018-08-05T17:22:57 Z Kubalionzzale Horses (IOI15_horses) C++14
34 / 100
 1500 ms 45448 KB 
#include "horses.h"
#include <algorithm>

int n;
long long int mod = 1e9 + 7;

long long int product[2000010] = { 0 };
long long int mediumProduct[2000010] = { 0 };
int curBest[2000010] = { 0 };
int x[500010], y[500010];

void constructProduct(int low, int high, int pos)
{
    if (low == high)
    {
        product[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    constructProduct(low, mid, pos * 2 + 1);
    constructProduct(mid + 1, high, pos * 2 + 2);

    product[pos] = (product[pos * 2 + 1] * product[pos * 2 + 2]) % mod;
}

void updateProduct(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        product[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    updateProduct(qpoint, low, mid, pos * 2 + 1);
    updateProduct(qpoint, mid + 1, high, pos * 2 + 2);

    product[pos] = (product[pos * 2 + 1] * product[pos * 2 + 2]) % mod;
}

long long int queryProduct(int low, int high, int qlow, int qhigh, int pos)
{
    if (high < qlow || low > qhigh)
        return 1;

    if (qlow <= low && high <= qhigh)
    {
        return product[pos];
    }

    int mid = low + (high - low) / 2;

    return ((queryProduct(low, mid, qlow, qhigh, pos * 2 + 1) * queryProduct(mid + 1, high, qlow, qhigh, pos * 2 + 2)) % mod);
}

void constructMediumProduct(int low, int high, int pos)
{
    if (low == high)
    {
        mediumProduct[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    constructMediumProduct(low, mid, pos * 2 + 1);
    constructMediumProduct(mid + 1, high, pos * 2 + 2);

    long long int val = mediumProduct[pos * 2 + 1] * mediumProduct[pos * 2 + 2];

    if (val > 1e9)
        mediumProduct[pos] = 0;
    else
        mediumProduct[pos] = val;
}

void updateMediumProduct(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        mediumProduct[pos] = x[low] * 1LL;
        return;
    }

    int mid = low + (high - low) / 2;

    constructMediumProduct(low, mid, pos * 2 + 1);
    constructMediumProduct(mid + 1, high, pos * 2 + 2);

    long long int val = mediumProduct[pos * 2 + 1] * mediumProduct[pos * 2 + 2];

    if (val > 1e9)
        mediumProduct[pos] = 0;
    else
        mediumProduct[pos] = val;
}

long long int queryMediumProduct(int low, int high, int qlow, int qhigh, int pos)
{
    if (high < qlow || low > qhigh)
        return 1;

    if (qlow <= low && high <= qhigh)
    {
        return mediumProduct[pos];
    }

    int mid = low + (high - low) / 2;

    long long int val1 = queryMediumProduct(low, mid, qlow, qhigh, pos * 2 + 1);
    long long int val2 = queryMediumProduct(mid + 1, high, qlow, qhigh, pos * 2 + 2);

    if (val1 * val2 > 1e9)
        return 0;
    else
        return val1 * val2;
}

int getBetter(int one, int two)
{
    long long int producted;

    producted = queryMediumProduct(0, n - 1, one + 1, two, 0);

    if (producted == 0)
        return two;
    else
    {
        long double oneans = y[one];
        long double twoans = producted * y[two];

        if (oneans > twoans)
            return one;
        else
            return two;
    }
}

void constructAnswer(int low, int high, int pos)
{
    if (low == high)
    {
        curBest[pos] = low;
        return;
    }

    int mid = low + (high - low) / 2;

    constructAnswer(low, mid, pos * 2 + 1);
    constructAnswer(mid + 1, high, pos * 2 + 2);

    curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[pos * 2 + 2]);
}

void updateAnswer(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        curBest[pos] = low;
        return;
    }

    int mid = low + (high - low) / 2;

    updateAnswer(qpoint, low, mid, pos * 2 + 1);
    updateAnswer(qpoint, mid + 1, high, pos * 2 + 2);

    curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[pos * 2 + 2]);
}

int init(int N, int inx[], int iny[]) {
    n = N;

    for (int i = 0; i < n; ++i)
    {
        x[i] = inx[i];
        y[i] = iny[i];
    }

    constructProduct(0, n - 1, 0);
    constructMediumProduct(0, n - 1, 0),
    constructAnswer(0, n - 1, 0);

    return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
}

int updateX(int position, int val) {
    x[position] = val;

    updateProduct(position, 0, n - 1, 0);
    updateMediumProduct(position, 0, n - 1, 0);
    updateAnswer(position, 0, n - 1, 0);

	return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
}

int updateY(int position, int val) {
    y[position] = val;
    updateAnswer(position, 0, n - 1, 0);

	return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
}

Compilation message

horses.cpp: In function 'void constructMediumProduct(int, int, int)':
horses.cpp:77:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val > 1e9)
               ^~~
horses.cpp: In function 'void updateMediumProduct(int, int, int, int)':
horses.cpp:101:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val > 1e9)
               ^~~
horses.cpp: In function 'long long int queryMediumProduct(int, int, int, int, int)':
horses.cpp:122:14: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val1 * val2 > 1e9)
         ~~~~~^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:196:71: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:206:68: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:213:68: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 1 ms 560 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 0 ms 564 KB Output is correct
8 Correct 3 ms 564 KB Output is correct
9 Correct 3 ms 564 KB Output is correct
10 Correct 3 ms 564 KB Output is correct
11 Correct 2 ms 564 KB Output is correct
12 Correct 2 ms 564 KB Output is correct
13 Correct 3 ms 564 KB Output is correct
14 Correct 3 ms 564 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 3 ms 564 KB Output is correct
17 Correct 2 ms 564 KB Output is correct
18 Correct 3 ms 564 KB Output is correct
19 Correct 3 ms 564 KB Output is correct
20 Correct 2 ms 680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 680 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 688 KB Output is correct
5 Correct 3 ms 688 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 3 ms 688 KB Output is correct
8 Correct 3 ms 688 KB Output is correct
9 Correct 2 ms 688 KB Output is correct
10 Correct 2 ms 688 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 688 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 3 ms 688 KB Output is correct
17 Correct 3 ms 688 KB Output is correct
18 Correct 2 ms 688 KB Output is correct
19 Correct 2 ms 688 KB Output is correct
20 Correct 3 ms 688 KB Output is correct
21 Correct 2 ms 688 KB Output is correct
22 Correct 3 ms 688 KB Output is correct
23 Correct 11 ms 688 KB Output is correct
24 Correct 10 ms 688 KB Output is correct
25 Correct 14 ms 688 KB Output is correct
26 Correct 11 ms 728 KB Output is correct
27 Correct 8 ms 756 KB Output is correct
28 Correct 12 ms 772 KB Output is correct
29 Correct 12 ms 792 KB Output is correct
30 Correct 14 ms 800 KB Output is correct
31 Correct 5 ms 820 KB Output is correct
32 Correct 9 ms 836 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 30288 KB Output is correct
2 Execution timed out 1553 ms 40228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 40228 KB Output is correct
2 Correct 3 ms 40228 KB Output is correct
3 Correct 3 ms 40228 KB Output is correct
4 Correct 3 ms 40228 KB Output is correct
5 Correct 3 ms 40228 KB Output is correct
6 Correct 2 ms 40228 KB Output is correct
7 Correct 4 ms 40228 KB Output is correct
8 Correct 3 ms 40228 KB Output is correct
9 Correct 2 ms 40228 KB Output is correct
10 Correct 3 ms 40228 KB Output is correct
11 Correct 2 ms 40228 KB Output is correct
12 Correct 2 ms 40228 KB Output is correct
13 Correct 3 ms 40228 KB Output is correct
14 Correct 3 ms 40228 KB Output is correct
15 Correct 2 ms 40228 KB Output is correct
16 Correct 2 ms 40228 KB Output is correct
17 Correct 2 ms 40228 KB Output is correct
18 Correct 2 ms 40228 KB Output is correct
19 Correct 3 ms 40228 KB Output is correct
20 Correct 2 ms 40228 KB Output is correct
21 Correct 3 ms 40228 KB Output is correct
22 Correct 3 ms 40228 KB Output is correct
23 Correct 11 ms 40228 KB Output is correct
24 Correct 16 ms 40228 KB Output is correct
25 Correct 10 ms 40228 KB Output is correct
26 Correct 11 ms 40228 KB Output is correct
27 Correct 12 ms 40228 KB Output is correct
28 Correct 14 ms 40228 KB Output is correct
29 Correct 15 ms 40228 KB Output is correct
30 Correct 16 ms 40228 KB Output is correct
31 Correct 5 ms 40228 KB Output is correct
32 Correct 9 ms 40228 KB Output is correct
33 Execution timed out 1573 ms 44428 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 44428 KB Output is correct
2 Correct 2 ms 44428 KB Output is correct
3 Correct 2 ms 44428 KB Output is correct
4 Correct 2 ms 44428 KB Output is correct
5 Correct 2 ms 44428 KB Output is correct
6 Correct 3 ms 44428 KB Output is correct
7 Correct 3 ms 44428 KB Output is correct
8 Correct 2 ms 44428 KB Output is correct
9 Correct 2 ms 44428 KB Output is correct
10 Correct 2 ms 44428 KB Output is correct
11 Correct 3 ms 44428 KB Output is correct
12 Correct 2 ms 44428 KB Output is correct
13 Correct 2 ms 44428 KB Output is correct
14 Correct 4 ms 44428 KB Output is correct
15 Correct 2 ms 44428 KB Output is correct
16 Correct 3 ms 44428 KB Output is correct
17 Correct 3 ms 44428 KB Output is correct
18 Correct 3 ms 44428 KB Output is correct
19 Correct 2 ms 44428 KB Output is correct
20 Correct 2 ms 44428 KB Output is correct
21 Correct 4 ms 44428 KB Output is correct
22 Correct 3 ms 44428 KB Output is correct
23 Correct 8 ms 44428 KB Output is correct
24 Correct 11 ms 44428 KB Output is correct
25 Correct 7 ms 44428 KB Output is correct
26 Correct 7 ms 44428 KB Output is correct
27 Correct 8 ms 44428 KB Output is correct
28 Correct 14 ms 44428 KB Output is correct
29 Correct 12 ms 44428 KB Output is correct
30 Correct 11 ms 44428 KB Output is correct
31 Correct 5 ms 44428 KB Output is correct
32 Correct 8 ms 44428 KB Output is correct
33 Correct 647 ms 45448 KB Output is correct
34 Execution timed out 1567 ms 45448 KB Time limit exceeded
35 Halted 0 ms 0 KB -