Submission #1026869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026869		TraianDanciu	Horses (IOI15_horses)	C++17	17 / 100	722 ms	70856 KiB

horses

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

#define MAXN 500000
#define MOD 1000000007

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 % MOD;
    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;
  if(qleft <= middle && middle < qright) {
    ans = max(_query(2 * node + 1, left, middle),
              _query(2 * node + 2, middle + 1, right));
  } else if(qleft <= middle) {
    ans = _query(2 * node + 1, left, middle);
  } else {
    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 (stderr)

horses.cpp: In function 'int lgpow(int, int)':
horses.cpp:11:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |       r = 1LL * r * a % MOD;
      |                       ^
horses.cpp:13:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   13 |     a = 1LL * a * a % MOD;
      |                     ^
horses.cpp: In member function 'Numar Numar::operator*(Numar)':
horses.cpp:32:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |     ret.val = 1LL * val * oth.val % MOD;
      |                                   ^
horses.cpp: In member function 'Numar Numar::operator/(Numar)':
horses.cpp:39:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   39 |     ret.val = 1LL * ret.val * lgpow(oth.val, MOD - 2) % MOD;
      |                                                       ^

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