Submission #1026922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026922		TraianDanciu	Horses (IOI15_horses)	C++17	100 / 100	792 ms	83516 KiB

horses

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

#define MAXN 500000
#define MOD 1000000007

void euclid(long long a, long long b, long long &x, long long &y) {
  long long x0, y0;

  if(b == 0) {
    x = 1;
    y = 0;
  } else {
    euclid(b, a % b, x0, y0);
    x = y0;
    y = x0 - a / b * y0;
  }
}

struct Numar {
  double ln;
  int val;

  Numar(int _val) {
    val = _val;
    ln = log2(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;
    long long x, y;
    euclid(oth.val, MOD, x, y);
    x %= MOD;
    if(x < 0) {
      x += MOD;
    }
    ret.val = 1LL * val * x % 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 member function 'Numar Numar::operator*(Numar)':
horses.cpp:33:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |     ret.val = 1LL * val * oth.val % MOD;
      |                                   ^
horses.cpp: In member function 'Numar Numar::operator/(Numar)':
horses.cpp:46:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |     ret.val = 1LL * val * x % MOD;
      |                             ^

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