Submission #285491

#	Time	Username	Problem	Language	Result	Execution time	Memory
285491		kevlee	Horses (IOI15_horses)	C++17	100 / 100	730 ms	68728 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int n, t[40];
ll x[500005], y[500005], bit[500005];
pll seg[2000005];
set <int> s;
void build(int id, int l, int r) {
  if (l == r) {
    seg[id] = {y[l], l};
    return;
  }
  int mid = (l + r) >> 1;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
  if (seg[id * 2 + 1].fi == max(seg[id * 2].fi, seg[id * 2 + 1].fi)) seg[id] = seg[id * 2 + 1];
  else seg[id] = seg[id * 2];
}
void point_update(int id, int l, int r, int pos) {
  if (l == r) {
    seg[id] = {y[l], l};
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) point_update(id * 2, l, mid, pos);
  else point_update(id * 2 + 1, mid + 1, r, pos);
  if (seg[id * 2 + 1].fi == max(seg[id * 2].fi, seg[id * 2 + 1].fi)) seg[id] = seg[id * 2 + 1];
  else seg[id] = seg[id * 2];
}
pll range_max(int id, int l, int r, int lq, int rq) {
  if (lq > r || rq < l) return {0, -1};
  if (lq <= l && r <= rq) return seg[id];
  int mid = (l + r) >> 1;
  pll L = range_max(id * 2, l, mid, lq, rq);
  pll R = range_max(id * 2 + 1, mid + 1, r, lq, rq);
  if (R.fi >= L.fi) return R;
  return L;
}
ll p(ll b, ll x) {
  if (x == 0) return 1;
  if (x == 1) return b % mod;
  ll tmp = p(b, x/2);
  if (x % 2 == 0) return tmp * tmp % mod;
  return (tmp * tmp) % mod * b % mod;
}
void update(int x, ll val) {
  for (x; x <= n; x += (x&(-x))) {
    bit[x] = bit[x] * val % mod;
  }
}
ll query(int x) {
  ll ret = 1;
  for (x; x > 0; x -= (x&(-x))) {
    ret = ret * bit[x] % mod;
  }
  return ret;
}
int calc(int pos) {
  ll ret = query(pos) * y[pos] % mod;
  return ret;
}
int solve() {
  int cur = 31;
  for (auto it = s.rbegin(); it != s.rend(); it++) {
    t[cur] = *it;
    cur--;
    if (cur < 0) break;
  }
  pll p = range_max(1, 1, n, 1, n);
  int bestpos = p.se;
  ll prod = 1;
  FOR(i, cur + 1, 31) {
    if (t[i] <= bestpos) continue;
    prod *= x[t[i]];
    if (prod > y[bestpos]) {
      bestpos = t[i];
      prod = 1;
    }
    ll required = y[bestpos] / prod + 1;
    pll res = range_max(1, 1, n, t[i], n);
    if (res.fi >= required) {
      bestpos = res.se;
      prod = 1;
    }
  }
  //cout << bestpos << endl;
  return calc(bestpos);
}
int init(int N, int X[], int Y[]) {
	n = N;
  FOR(i, 0, n-1) {
    x[i + 1] = X[i];
    y[i + 1] = Y[i];
    bit[i + 1] = 1;
  }
  FOR(i, 1, n) {
    update(i, x[i]);
    if (x[i] > 1) s.insert(i);
  }
  build(1, 1, n);
  return solve();
}

int updateX(int pos, int val) {	
  pos++;
	ll mul = 1LL * val * p(x[pos], mod - 2) % mod;
  update(pos, mul);
  if (x[pos] == 1 && val > 1) {
    s.insert(pos);
  } else if (x[pos] > 1 && val == 1) {
    s.erase(pos);
  }
  x[pos] = val;
  return solve();
}

int updateY(int pos, int val) {
  pos++;
	y[pos] = val;
  point_update(1, 1, n, pos);
  return solve();
}

Compilation message (stderr)

horses.cpp: In function 'long long int p(long long int, long long int)':
horses.cpp:60:16: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   60 | ll p(ll b, ll x) {
      |                ^
horses.cpp:26:4: note: shadowed declaration is here
   26 | ll x[500005], y[500005], bit[500005];
      |    ^
horses.cpp: In function 'void update(int, long long int)':
horses.cpp:67:26: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   67 | void update(int x, ll val) {
      |                          ^
horses.cpp:26:4: note: shadowed declaration is here
   26 | ll x[500005], y[500005], bit[500005];
      |    ^
horses.cpp:68:8: warning: statement has no effect [-Wunused-value]
   68 |   for (x; x <= n; x += (x&(-x))) {
      |        ^
horses.cpp: In function 'long long int query(int)':
horses.cpp:72:15: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   72 | ll query(int x) {
      |               ^
horses.cpp:26:4: note: shadowed declaration is here
   26 | ll x[500005], y[500005], bit[500005];
      |    ^
horses.cpp:74:8: warning: statement has no effect [-Wunused-value]
   74 |   for (x; x > 0; x -= (x&(-x))) {
      |        ^
horses.cpp: In function 'int calc(int)':
horses.cpp:81:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |   return ret;
      |          ^~~
horses.cpp: In function 'int solve()':
horses.cpp:15:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define se second
      |            ^
horses.cpp:91:19: note: in expansion of macro 'se'
   91 |   int bestpos = p.se;
      |                   ^~
horses.cpp:15:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define se second
      |            ^
horses.cpp:103:21: note: in expansion of macro 'se'
  103 |       bestpos = res.se;
      |                     ^~

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