Submission #285461

#	Time	Username	Problem	Language	Result	Execution time	Memory
285461		kevlee	Horses (IOI15_horses)	C++17	17 / 100	143 ms	29700 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;
ll x[500005], y[500005], bit[500005];
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() {
  FOR(i, max(1, n - 32), n) {
    ll prod = 1;
    bool ok = true;
    FOR(j, i+1, n) {
      prod *= x[j];
      if (prod > y[i]) {
        ok = false;
        break;
      }
      if (prod * y[j] > y[i]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      return calc(i);
    }
  }
  return -1;
}
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]);
  }
  return solve();
}

int updateX(int pos, int val) {	
  pos++;
	ll mul = 1LL * val * p(x[pos], mod - 2);
  update(pos, mul);
  return solve();
}

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

Compilation message (stderr)

horses.cpp: In function 'long long int p(long long int, long long int)':
horses.cpp:27:16: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   27 | 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:34:26: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   34 | 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:35:8: warning: statement has no effect [-Wunused-value]
   35 |   for (x; x <= n; x += (x&(-x))) {
      |        ^
horses.cpp: In function 'long long int query(int)':
horses.cpp:39:15: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   39 | ll query(int x) {
      |               ^
horses.cpp:26:4: note: shadowed declaration is here
   26 | ll x[500005], y[500005], bit[500005];
      |    ^
horses.cpp:41:8: warning: statement has no effect [-Wunused-value]
   41 |   for (x; x > 0; x -= (x&(-x))) {
      |        ^
horses.cpp: In function 'int calc(int)':
horses.cpp:48:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |   return ret;
      |          ^~~

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