Submission #1026767

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1026767	2024-07-18T10:50:55 Z	TraianDanciu	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KB

horses

#include "horses.h"
#include <math.h>

#define MAXN 500000
#define MOD 100000007

#define int long long

int lgpow(int a, int n) {
  int r = 1;
  while(n > 0) {
    if(n % 2) {
      r = 1LL * r * a % MOD;
    }
    a = 1LL * a * a % MOD;
    n /= 2;
  }
  return r;
}

struct Numar {
  double ln;
  int val;

  Numar(int _val) {
    val = _val;
    ln = log(val);
  }

  Numar() {}

  inline Numar operator *(Numar oth) {
    Numar ret;
    ret.val = 1LL * val * oth.val % MOD;
    ret.ln = ln + oth.ln;
    return ret;
  }

  inline Numar operator /(Numar oth) {
    Numar ret;
    ret.val = 1LL * ret.val * lgpow(oth.val, MOD - 2) % MOD;
    ret.ln = ln - oth.ln;
    return ret;
  }

  inline bool operator <(Numar oth) {
    return ln < oth.ln;
  }
};

static inline Numar max(Numar a, Numar b) {
  return a < b ? b : a;
}

Numar aint[4 * MAXN], lazy[4 * MAXN], qval;
int n, x[MAXN], y[MAXN], qleft, qright;

void propagate(int node, int left, int right) {
  aint[node] = aint[node] * lazy[node];
  if(left < right) {
    lazy[2 * node + 1] = lazy[2 * node + 1] * lazy[node];
    lazy[2 * node + 2] = lazy[2 * node + 2] * lazy[node];
  }
  lazy[node] = Numar(1);
}

void _update(int node, int left, int right) {
  int middle;

  propagate(node, left, right);
  if(qleft <= left && right <= qright) {
    lazy[node] = lazy[node] * qval;
    propagate(node, left, right);
  } else {
    middle = (left + right) / 2;

    propagate(2 * node + 1, left, middle);
    propagate(2 * node + 2, middle + 1, right);

    if(qleft <= middle) {
      _update(2 * node + 1, left, middle);
    }
    if(middle < qright) {
      _update(2 * node + 2, middle + 1, right);
    }

    aint[node] = max(aint[2 * node + 1], aint[2 * node + 2]);
  }
}
void update(int _qleft, int _qright, Numar _qval) {
  qleft = _qleft;
  qright = _qright;
  qval = _qval;
  _update(0, 0, n - 1);
} 

Numar _query(int node, int left, int right) {
  int middle;
  Numar ans;

  propagate(node, left, right);

  if(qleft <= left && right <= qright) {
    return aint[node];
  }

  middle = (left + right) / 2;
  ans = Numar(1);

  if(qleft <= middle) {
    ans = max(ans, _query(2 * node + 1, left, middle));
  }
  if(middle < qright) {
    ans = max(ans, _query(2 * node + 2, middle + 1, right));
  }

  return ans;
}
Numar query(int _qleft, int _qright) {
  qleft = _qleft;
  qright = _qright;
  return _query(0, 0, n - 1);
}

int init(int _n, int _x[], int _y[]) {
  int i;

  n = _n;
  for(i = 0; i < 4 * n; i++) {
    aint[i] = lazy[i] = Numar(1);
  }

  for(i = 0; i < n; i++) {
    x[i] = _x[i];
    update(i, n - 1, Numar(x[i]));
    y[i] = _y[i];
    update(i, i, Numar(y[i]));
  }

  return query(0, n - 1).val;
}

int updateX(int pos, int val) {
  update(pos, n - 1, Numar(val) / Numar(x[pos]));
  x[pos] = val;
  return query(0, n - 1).val;
}

int updateY(int pos, int val) {
  update(pos, pos, Numar(val) / Numar(y[pos]));
  y[pos] = val;
  return query(0, n - 1).val;
}

Compilation message

/usr/bin/ld: /tmp/cclP8K0j.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x113): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x16d): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status