Submission #802360

#	Time	Username	Problem	Language	Result	Execution time	Memory
802360		erray	Horses (IOI15_horses)	C++17	0 / 100	245 ms	38512 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi15_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

struct SegTree {
  vector<int> mx;
  int n;
  SegTree(int _n) : n(_n) {
    mx.resize(2 * n + 1);
  }
  SegTree() { }
  int get(int l) {
    l += n;
    int r = 2 * n;
    int res = 0;
    while (l < r) {
      if (l & 1) {
        res = max(res, mx[l++]);
      }
      if (r & 1) {
        res = max(res, mx[--r]);
      }
      l >>= 1, r >>= 1;
    }
    return res;
  }
  void modify(int x, int v) {
    mx[x += n] = v;
    while (x > 1) {
      mx[x >> 1] = max(mx[x], mx[x ^ 1]);
      x >>= 1;
    }
  }
};

constexpr int md = int(1e9) + 7;
struct Mint {
  int val = 0;
  Mint() { }
  template<typename T>
  Mint(T v) {
    val = int(v % md);
    if (val < 0) {
      val += md;
    }
  }
  int& operator()() { return val; }
  Mint& operator+=(Mint x) {
    if ((val += x.val) > md) {
      val -= md;
    }
    return *this;
  }
  Mint& operator*=(Mint x) {
    val = int(1LL * val * x.val % md);
    return *this;
  }
  Mint power(Mint x, int p) {
    Mint res = 1;
    while (p > 0) {
      if (p & 1) {
        res *= x;
      }
      x *= x;
      p >>= 1;
    }
    return res;
  }
  Mint& operator/=(Mint x) {
    //debug(x, power(x, md - 2));
    return *this *= power(x, md - 2);
  }
};
Mint operator+(Mint x, Mint y) {
  return x += y;
}
Mint operator*(Mint x, Mint y) {
  return x *= y;
}
Mint operator/(Mint x, Mint y) {
  return x /= y;
}
string to_string(Mint x) {
  return to_string(x());
}
int N;
set<int> act;
SegTree st;
vector<int> X, Y;
vector<Mint> inv;
Mint tot = 1;
int Calc() {
  //assert(!act.empty());
  if (act.empty()) {
    return st.get(0);
  }
  auto it = act.end();
  long long mul = 1;
  vector<int> t;
  while (it != act.begin() && mul < int(1e9)) {
    it = prev(it);
    mul *= X[*it];
    t.push_back(*it);
  }
  debug(t);
  reverse(t.begin(), t.end());
  long long mx = -1;
  mul = 1;
  Mint pref = tot;
  bool first = true;
  for (auto i : t) {
    if (!first) pref *= inv[i];
    mx = max(mx, mul * st.get(i));
    mul *= X[i];
    first = false;    
  }
  return (pref * mx)();
}

int init(int __N, int __X[], int __Y[]) {
	N = __N;
  X = inverse_fuck(__X, N);
  Y = inverse_fuck(__Y, N); 
  inv.resize(N);
  for (int i = 0; i < N; ++i) {
    inv[i] = Mint(1) / X[i];
    tot *= X[i];
    if (X[i] != 1) {
      act.insert(i);
    }
  }
  st = SegTree(N);
  for (int i = 0; i < N; ++i) {
    st.modify(i, Y[i]);
  }
  debug(X, inv, tot);
  return Calc();
}

int updateX(int pos, int val) {	
	if (X[pos] != val) {
    if (X[pos] == 1) { //replace set with sth else if it get's tle 
      act.insert(pos);
    } else if(val == 1) {
      act.erase(pos);
    }
    tot *= inv[pos] * val;
    X[pos] = val;
    inv[pos] = Mint(1) / X[pos];
  }
  return Calc();
}

int updateY(int pos, int val) {
  st.modify(pos, val);
	return Calc();
}

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