| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 802359 |
2023-08-02T11:54:10 Z |
erray |
Horses (IOI15_horses) |
C++17 |
|
253 ms |
38456 KB |
#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());
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();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
253 ms |
38456 KB |
Output is correct |
| 2 |
Correct |
242 ms |
38448 KB |
Output is correct |
| 3 |
Incorrect |
215 ms |
38456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
