제출 #890703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890703		AkibAzmain	말 (IOI15_horses)	C++17	17 / 100	321 ms	44836 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;

const ll MOD = ((ll) 1e9) + 7;

ll n;
vector < ll > ma;
vector < ll > bit;
int sts = 1;
vector < ll > mst;
set < ll > cs;

ll
binpow (ll a, ll b)
{
  ll ans = 1;
  while (b)
    {
      if (b % 2) (ans *= a) %= MOD;
      b /= 2;
      if (b) (a *= a) %= MOD;
    }
  return ans;
}

ll
bitp (ll x)
{
  ll ans = 1;
  while (x >= 0)
    {
      (ans *= bit[x]) %= MOD;
      x -= (x + 1) & -(x + 1);
    }
  return ans;
}

ll
bitr (ll l, ll r)
{
  ll ans = bitp (r);
  if (l) (ans *= binpow (bitp (l - 1), MOD - 2)) %= MOD;
  return ans;
}

ll
stm (ll l, ll r)
{
  l += sts, r += sts;
  ll mx = -1;
  while (l <= r)
    {
      if (l % 2 == 1) mx = max (mx, mst[l++]);
      if (r % 2 == 0) mx = max (mx, mst[r--]);
      l /= 2, r /= 2;
    }
  return mx;
}

int
calc ()
{
  auto it = cs.end (), pit = prev (it);
  ll vl = 0;
  while (vl < MOD)
    {
      --it, --pit;
      vl = max (vl, mst[sts + *it]);
      vl *= ma[*it];
      if (vl >= MOD) break;
      if (*it && *pit + 1 <= *it - 1)
        vl = max (vl, stm (*pit + 1, *it - 1));
      if (!*pit) ++pit;
      if (!*it) break;
    }
  vl %= MOD;
  if (*it)
    (vl *= bitp (*it - 1)) %= MOD;
  return vl;
}

int init(int N, int x[], int y[]) {
  n = N;
  ma.resize (n);
  bit.resize (n);
  while (sts < n) sts *= 2;
  mst.resize (sts * 2);
  for (int i = 0; i < n; ++i)
    {
      if (x[i] > 1) cs.insert (i);
      ma[i] = x[i];
      mst[sts + i] = y[i];
      bit[i] = x[i] * (i ? bitr (i - ((i + 1) & -(i + 1)) + 1, i - 1) : 1ll);
    }
  for (int i = sts - 1; i > 0; --i) mst[i] = max (mst[i * 2], mst[i * 2 + 1]);
  cs.insert (0);
  cs.insert (n - 1);
  return calc ();
}

int updateX(int pos, int val) {
  cs.erase (pos);
  if (val > 1) cs.insert (pos);
  ll dl = val * binpow (ma[pos], MOD - 2) % MOD;
  ma[pos] = val;
  for (int i = pos; i < n; i += (i + 1) & -(i + 1)) (bit[i] *= dl) %= MOD;
  cs.insert (0);
  cs.insert (n - 1);
  return calc ();
}

int updateY(int pos, int val) {
  int i = sts + pos;
  mst[i] = val;
  for (i /= 2; i > 0; i /= 2) mst[i] = max (mst[i * 2], mst[i * 2 + 1]);
  return calc ();
}

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

horses.cpp: In function 'int calc()':
horses.cpp:81:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |   return vl;
      |          ^~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23