oj.uz

Submission #1026874

# Submission time Handle Problem Language Result Execution time Memory
1026874 2024-07-18T12:41:35 Z TraianDanciu Horses (IOI15_horses) C++17
17 / 100
 708 ms 71732 KB 
#include "horses.h"
#include <math.h>

#define MAXN 500000
#define MOD 1000000007

int euclid(int a, int b, int &x, int &y) {
  int x0, y0, ret;

  if(b == 0) {
    x = 1;
    y = 0;
    return a;
  }

  ret = euclid(b, a % b, x0, y0);
  x = y0;
  y = x0 - a / b * y0;

  return ret;
}

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;
    int x, y;
    euclid(oth.val, MOD, x, y);
    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

horses.cpp: In member function 'Numar Numar::operator*(Numar)':
horses.cpp:36:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   36 |     ret.val = 1LL * val * oth.val % MOD;
      |                                   ^
horses.cpp: In member function 'Numar Numar::operator/(Numar)':
horses.cpp:45:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |     ret.val = 1LL * val * x % MOD;
      |                             ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 0 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 6492 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 708 ms 71732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6580 KB Output is correct
11 Correct 1 ms 6540 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6580 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 6492 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6648 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 6492 KB Output isn't correct
22 Halted 0 ms 0 KB -