제출 #434454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434454		alextodoran	말 (IOI15_horses)	C++17	100 / 100	1235 ms	27656 KiB

horses

/**
 ____ ____ ____ ____ ____
||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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23