답안 #64805 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64805	2018-08-05T17:31:15 Z	Kubalionzzale	말 (IOI15_horses)	C++14	100 / 100	1424 ms	115544 KB

horses

#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];

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 constructProduct(int low, int high, int pos)
{
    if (low == high)
    {
        product[pos] = x[low] * 1LL;
        mediumProduct[pos] = x[low] * 1LL;
        curBest[pos] = low;
        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;
    curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[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 updateProduct(int qpoint, int low, int high, int pos)
{
    if (qpoint < low || qpoint > high)
        return;

    if (low == high)
    {
        product[pos] = x[low] * 1LL;
        mediumProduct[pos] = x[low] * 1LL;
        curBest[pos] = low;
        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;
    curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[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 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 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);

    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);

	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 'long long int queryMediumProduct(int, int, int, int, int)':
horses.cpp:27:14: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val1 * val2 > 1e9)
         ~~~~~^~~~~~
horses.cpp: In function 'void constructProduct(int, int, int)':
horses.cpp:72:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     if (val > 1e9)
               ^~~
horses.cpp: In function 'void updateProduct(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 'int init(int, int*, int*)':
horses.cpp:152: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:160: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:167: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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	4 ms	356 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	4 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	3 ms	620 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	3 ms	620 KB	Output is correct
13	Correct	3 ms	620 KB	Output is correct
14	Correct	3 ms	620 KB	Output is correct
15	Correct	3 ms	620 KB	Output is correct
16	Correct	3 ms	620 KB	Output is correct
17	Correct	3 ms	620 KB	Output is correct
18	Correct	3 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	3 ms	620 KB	Output is correct
3	Correct	4 ms	624 KB	Output is correct
4	Correct	2 ms	624 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	3 ms	624 KB	Output is correct
7	Correct	3 ms	624 KB	Output is correct
8	Correct	3 ms	624 KB	Output is correct
9	Correct	2 ms	624 KB	Output is correct
10	Correct	3 ms	624 KB	Output is correct
11	Correct	3 ms	624 KB	Output is correct
12	Correct	3 ms	624 KB	Output is correct
13	Correct	2 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	2 ms	624 KB	Output is correct
16	Correct	3 ms	624 KB	Output is correct
17	Correct	2 ms	624 KB	Output is correct
18	Correct	3 ms	744 KB	Output is correct
19	Correct	2 ms	744 KB	Output is correct
20	Correct	3 ms	744 KB	Output is correct
21	Correct	3 ms	744 KB	Output is correct
22	Correct	2 ms	744 KB	Output is correct
23	Correct	5 ms	744 KB	Output is correct
24	Correct	6 ms	744 KB	Output is correct
25	Correct	5 ms	744 KB	Output is correct
26	Correct	5 ms	744 KB	Output is correct
27	Correct	4 ms	744 KB	Output is correct
28	Correct	5 ms	744 KB	Output is correct
29	Correct	4 ms	744 KB	Output is correct
30	Correct	4 ms	744 KB	Output is correct
31	Correct	5 ms	744 KB	Output is correct
32	Correct	6 ms	744 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	696 ms	29932 KB	Output is correct
2	Correct	764 ms	31560 KB	Output is correct
3	Correct	964 ms	35388 KB	Output is correct
4	Correct	828 ms	42848 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	42848 KB	Output is correct
2	Correct	2 ms	42848 KB	Output is correct
3	Correct	3 ms	42848 KB	Output is correct
4	Correct	2 ms	42848 KB	Output is correct
5	Correct	2 ms	42848 KB	Output is correct
6	Correct	2 ms	42848 KB	Output is correct
7	Correct	3 ms	42848 KB	Output is correct
8	Correct	2 ms	42848 KB	Output is correct
9	Correct	3 ms	42848 KB	Output is correct
10	Correct	2 ms	42848 KB	Output is correct
11	Correct	3 ms	42848 KB	Output is correct
12	Correct	3 ms	42848 KB	Output is correct
13	Correct	2 ms	42848 KB	Output is correct
14	Correct	2 ms	42848 KB	Output is correct
15	Correct	2 ms	42848 KB	Output is correct
16	Correct	2 ms	42848 KB	Output is correct
17	Correct	3 ms	42848 KB	Output is correct
18	Correct	3 ms	42848 KB	Output is correct
19	Correct	3 ms	42848 KB	Output is correct
20	Correct	2 ms	42848 KB	Output is correct
21	Correct	2 ms	42848 KB	Output is correct
22	Correct	3 ms	42848 KB	Output is correct
23	Correct	4 ms	42848 KB	Output is correct
24	Correct	6 ms	42848 KB	Output is correct
25	Correct	4 ms	42848 KB	Output is correct
26	Correct	4 ms	42848 KB	Output is correct
27	Correct	5 ms	42848 KB	Output is correct
28	Correct	4 ms	42848 KB	Output is correct
29	Correct	3 ms	42848 KB	Output is correct
30	Correct	3 ms	42848 KB	Output is correct
31	Correct	5 ms	42848 KB	Output is correct
32	Correct	5 ms	42848 KB	Output is correct
33	Correct	330 ms	42848 KB	Output is correct
34	Correct	349 ms	46044 KB	Output is correct
35	Correct	248 ms	51452 KB	Output is correct
36	Correct	223 ms	51572 KB	Output is correct
37	Correct	235 ms	51572 KB	Output is correct
38	Correct	217 ms	54484 KB	Output is correct
39	Correct	230 ms	56668 KB	Output is correct
40	Correct	253 ms	62492 KB	Output is correct
41	Correct	200 ms	64608 KB	Output is correct
42	Correct	219 ms	66704 KB	Output is correct
43	Correct	182 ms	72908 KB	Output is correct
44	Correct	213 ms	79264 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	79264 KB	Output is correct
2	Correct	3 ms	79264 KB	Output is correct
3	Correct	3 ms	79264 KB	Output is correct
4	Correct	2 ms	79264 KB	Output is correct
5	Correct	3 ms	79264 KB	Output is correct
6	Correct	3 ms	79264 KB	Output is correct
7	Correct	3 ms	79264 KB	Output is correct
8	Correct	2 ms	79264 KB	Output is correct
9	Correct	2 ms	79264 KB	Output is correct
10	Correct	2 ms	79264 KB	Output is correct
11	Correct	2 ms	79264 KB	Output is correct
12	Correct	3 ms	79264 KB	Output is correct
13	Correct	2 ms	79264 KB	Output is correct
14	Correct	3 ms	79264 KB	Output is correct
15	Correct	3 ms	79264 KB	Output is correct
16	Correct	2 ms	79264 KB	Output is correct
17	Correct	3 ms	79264 KB	Output is correct
18	Correct	2 ms	79264 KB	Output is correct
19	Correct	2 ms	79264 KB	Output is correct
20	Correct	3 ms	79264 KB	Output is correct
21	Correct	3 ms	79264 KB	Output is correct
22	Correct	3 ms	79264 KB	Output is correct
23	Correct	5 ms	79264 KB	Output is correct
24	Correct	5 ms	79264 KB	Output is correct
25	Correct	5 ms	79264 KB	Output is correct
26	Correct	4 ms	79264 KB	Output is correct
27	Correct	6 ms	79264 KB	Output is correct
28	Correct	6 ms	79264 KB	Output is correct
29	Correct	5 ms	79264 KB	Output is correct
30	Correct	4 ms	79264 KB	Output is correct
31	Correct	6 ms	79264 KB	Output is correct
32	Correct	4 ms	79264 KB	Output is correct
33	Correct	593 ms	80256 KB	Output is correct
34	Correct	851 ms	80256 KB	Output is correct
35	Correct	1016 ms	80380 KB	Output is correct
36	Correct	880 ms	80472 KB	Output is correct
37	Correct	323 ms	80472 KB	Output is correct
38	Correct	311 ms	80472 KB	Output is correct
39	Correct	240 ms	80472 KB	Output is correct
40	Correct	218 ms	80472 KB	Output is correct
41	Correct	226 ms	80472 KB	Output is correct
42	Correct	218 ms	82548 KB	Output is correct
43	Correct	201 ms	84516 KB	Output is correct
44	Correct	197 ms	90380 KB	Output is correct
45	Correct	238 ms	92512 KB	Output is correct
46	Correct	221 ms	94484 KB	Output is correct
47	Correct	187 ms	100732 KB	Output is correct
48	Correct	183 ms	107132 KB	Output is correct
49	Correct	1314 ms	113300 KB	Output is correct
50	Correct	1424 ms	115496 KB	Output is correct
51	Correct	788 ms	115536 KB	Output is correct
52	Correct	566 ms	115536 KB	Output is correct
53	Correct	1090 ms	115536 KB	Output is correct
54	Correct	742 ms	115536 KB	Output is correct
55	Correct	455 ms	115536 KB	Output is correct
56	Correct	507 ms	115536 KB	Output is correct
57	Correct	723 ms	115536 KB	Output is correct
58	Correct	617 ms	115544 KB	Output is correct
59	Correct	229 ms	115544 KB	Output is correct

답안 #64805

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 23.0 / 23.0

Subtask #5 23.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
23.0 / 23.0

Subtask #5
23.0 / 23.0