oj.uz

Submission #434454

# Submission time Handle Problem Language Result Execution time Memory
434454 2021-06-21T10:22:48 Z alextodoran Horses (IOI15_horses) C++17
100 / 100
 1235 ms 27656 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

typedef long long ll;

const int N_MAX = 500000;
const int BITS = 19;

const int MOD = 1e9+7;

int pwr (int a, int b)
{
    if(b == 0)
        return 1;
    if(b & 1)
        return 1LL * a * pwr(a, (b ^ 1)) % MOD;
    int aux = pwr(a, (b >> 1));
    return 1LL * aux * aux % MOD;
}

int n;

int x[N_MAX + 2];
int y[N_MAX + 2];

int SGT[N_MAX * 4 + 2];

void build (int node, int l, int r)
{
    if(l == r)
    {
        SGT[node] = y[l];
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);
    SGT[node] = max(SGT[lSon], SGT[rSon]);
}
void build ()
{
    build(1, 1, n);
}

void updateSGT (int node, int l, int r, int upos, int uval)
{
    if(l == r)
    {
        SGT[node] = uval;
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if(upos <= mid)
        updateSGT(lSon, l, mid, upos, uval);
    else
        updateSGT(rSon, mid + 1, r, upos, uval);
    SGT[node] = max(SGT[lSon], SGT[rSon]);
}
void updateSGT (int upos, int uval)
{
    updateSGT(1, 1, n, upos, uval);
}

int querySGT (int node, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return SGT[node];
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    int answer = INT_MIN;
    if(ql <= mid)
        answer = max(answer, querySGT(lSon, l, mid, ql, qr));
    if(mid + 1 <= qr)
        answer = max(answer, querySGT(rSon, mid + 1, r, ql, qr));
    return answer;
}
int querySGT (int ql, int qr)
{
    return querySGT(1, 1, n, ql, qr);
}

int BIT[N_MAX + 2];

void updateBIT (int upos, int uval)
{
    for(int i = upos; i <= n; i += i & -i)
        BIT[i] = 1LL * BIT[i] * uval % MOD;
}

int queryBIT (int upos)
{
    int answer = 1;
    for(int i = upos; i >= 1; i -= i & -i)
        answer = 1LL * answer * BIT[i] % MOD;
    return answer;
}

int query ()
{
    vector <pair <int, int>> segments;

    int prod = 1;
    int R = n;
    while(1 <= R)
    {
        int Rpref = queryBIT(R);
        int L = 0;
        int Lpref = 1;
        for(int bit = BITS - 1; bit >= 0; bit--)
            if(L + (1 << bit) < R && 1LL * Lpref * BIT[L + (1 << bit)] % MOD != Rpref)
            {
                L += (1 << bit);
                Lpref = 1LL * Lpref * BIT[L] % MOD;
            }
        L++;

        segments.push_back(make_pair(L, R));

        if(1000000000 / prod < x[L])
            break;
        prod *= x[L];
        R = L - 1;
    }
    reverse(segments.begin(), segments.end());

    prod = 1;
    ll answer = 0;
    for(pair <int, int> seg : segments)
    {
        int L = seg.first;
        int R = seg.second;

        if(L != segments.front().first)
            prod *= x[L];

        int bestY = querySGT(L, R);
        answer = max(answer, 1LL * prod * bestY);
    }

    answer = answer % MOD * queryBIT(segments.front().first) % MOD;
    return answer;
}

int init (int _n, int _x[], int _y[])
{
    n = _n;
    for(int i = 1; i <= n; i++)
        x[i] = _x[i - 1];
    for(int i = 1; i <= n; i++)
        y[i] = _y[i - 1];

    for(int i = 1; i <= n; i++)
        BIT[i] = 1;
    for(int i = 1; i <= n; i++)
        updateBIT(i, x[i]);

    build();

    return query();
}

int updateX (int upos, int uval)
{
    upos++;

    updateBIT(upos, pwr(x[upos], MOD - 2));
    x[upos] = uval;
    updateBIT(upos, x[upos]);

    return query();
}

int updateY (int upos, int uval)
{
    upos++;

    y[upos] = uval;
    updateSGT(upos, y[upos]);

    return query();
}

Compilation message

horses.cpp: In function 'int pwr(int, int)':
horses.cpp:26:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   26 |         return 1LL * a * pwr(a, (b ^ 1)) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:28:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   28 |     return 1LL * aux * aux % MOD;
      |            ~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void updateBIT(int, int)':
horses.cpp:99:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |         BIT[i] = 1LL * BIT[i] * uval % MOD;
      |                  ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int queryBIT(int)':
horses.cpp:106:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |         answer = 1LL * answer * BIT[i] % MOD;
      |                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int query()':
horses.cpp:125:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  125 |                 Lpref = 1LL * Lpref * BIT[L] % MOD;
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:143:13: warning: declaration of 'R' shadows a previous local [-Wshadow]
  143 |         int R = seg.second;
      |             ^
horses.cpp:115:9: note: shadowed declaration is here
  115 |     int R = n;
      |         ^
horses.cpp:153:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  153 |     return answer;
      |            ^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 372 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 292 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 3 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 8 ms 368 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 6 ms 332 KB Output is correct
32 Correct 6 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 15136 KB Output is correct
2 Correct 232 ms 15068 KB Output is correct
3 Correct 272 ms 15068 KB Output is correct
4 Correct 283 ms 15164 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 7 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 5 ms 316 KB Output is correct
32 Correct 8 ms 332 KB Output is correct
33 Correct 67 ms 18116 KB Output is correct
34 Correct 68 ms 18100 KB Output is correct
35 Correct 101 ms 25112 KB Output is correct
36 Correct 102 ms 24976 KB Output is correct
37 Correct 170 ms 16452 KB Output is correct
38 Correct 73 ms 17200 KB Output is correct
39 Correct 57 ms 16196 KB Output is correct
40 Correct 80 ms 20084 KB Output is correct
41 Correct 113 ms 16324 KB Output is correct
42 Correct 143 ms 16396 KB Output is correct
43 Correct 59 ms 20548 KB Output is correct
44 Correct 68 ms 20552 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 7 ms 376 KB Output is correct
28 Correct 4 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 312 KB Output is correct
31 Correct 6 ms 332 KB Output is correct
32 Correct 7 ms 332 KB Output is correct
33 Correct 937 ms 19048 KB Output is correct
34 Correct 218 ms 27656 KB Output is correct
35 Correct 281 ms 18892 KB Output is correct
36 Correct 305 ms 22756 KB Output is correct
37 Correct 65 ms 18120 KB Output is correct
38 Correct 69 ms 18116 KB Output is correct
39 Correct 99 ms 25096 KB Output is correct
40 Correct 95 ms 25004 KB Output is correct
41 Correct 190 ms 16364 KB Output is correct
42 Correct 77 ms 17208 KB Output is correct
43 Correct 60 ms 16240 KB Output is correct
44 Correct 76 ms 20156 KB Output is correct
45 Correct 109 ms 16268 KB Output is correct
46 Correct 124 ms 16276 KB Output is correct
47 Correct 54 ms 20548 KB Output is correct
48 Correct 56 ms 20560 KB Output is correct
49 Correct 229 ms 20260 KB Output is correct
50 Correct 181 ms 20180 KB Output is correct
51 Correct 336 ms 26916 KB Output is correct
52 Correct 207 ms 26436 KB Output is correct
53 Correct 1235 ms 18528 KB Output is correct
54 Correct 379 ms 19040 KB Output is correct
55 Correct 249 ms 17344 KB Output is correct
56 Correct 207 ms 21948 KB Output is correct
57 Correct 670 ms 17920 KB Output is correct
58 Correct 943 ms 18400 KB Output is correct
59 Correct 68 ms 20548 KB Output is correct