# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
583334 |
2022-06-25T08:48:26 Z |
Drew_ |
Horses (IOI15_horses) |
C++17 |
|
19 ms |
10776 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const int MAX = 5e3 + 69;
const ll inf = 1e9 + 5;
const int mod = 1e9 + 7;
template<int MOD = mod>
struct Mint
{
int val;
Mint() : val(0) {}
Mint(int64_t _val) : val((int)(_val % MOD)) { if (val < 0) val += MOD; }
Mint& operator+= (const Mint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; }
Mint& operator-= (const Mint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; }
Mint& operator*= (const Mint &rhs) { val = (int)(1ll * val * rhs.val % MOD); return *this; }
friend Mint fpow(Mint x, int64_t y)
{
Mint res = 1;
for (; y > 0; y >>= 1, x *= x)
{
if (y & 1)
res *= x;
}
return res;
}
friend Mint inverse(Mint x) { return fpow(x, MOD-2); }
Mint& operator/= (const Mint &rhs) { return *this *= inverse(rhs); }
friend Mint operator+ (Mint a, const Mint &b) { return a += b; }
friend Mint operator- (Mint a, const Mint &b) { return a -= b; }
friend Mint operator- (Mint a) { return 0 - a; }
friend Mint operator* (Mint a, const Mint &b) { return a *= b; }
friend Mint operator/ (Mint a, const Mint &b) { return a /= b; }
friend ostream& operator<< (ostream &os, const Mint &a) { return os << a.val; }
friend bool operator== (const Mint &a, const Mint &b) { return a.val == b.val; }
friend bool operator!= (const Mint &a, const Mint &b) { return a.val != b.val; }
};
struct Segtree1
{
int n;
Mint<> st[2 * MAX];
Segtree1() {}
Segtree1(int n_, int ar[]) : n(n_)
{
for (int i = 0; i < n; ++i)
st[i+n] = ar[i];
for (int i = n-1; i >= 0; --i)
st[i] = st[i << 1] * st[i << 1 | 1];
}
inline void modify(int p, int val)
{
for (st[p += n] = val; p > 1; p >>= 1)
st[p >> 1] = st[p] * st[p^1];
}
inline Mint<> query(int l, int r)
{
Mint<> res = 1;
for (l += n, r += n+1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) res *= st[l++];
if (r & 1) res *= st[--r];
}
return res;
}
} st1;
struct Segtree2
{
int n;
int st[2 * MAX];
Segtree2() {}
Segtree2(int n_, int ar[]) : n(n_)
{
for (int i = 0; i < n; ++i)
st[i+n] = ar[i];
for (int i = n-1; i >= 0; --i)
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
inline void modify(int p, int val)
{
for (st[p += n] = val; p > 1; p >>= 1)
st[p >> 1] = max(st[p], st[p^1]);
}
inline int query(int l, int r)
{
int res = 0;
for (l += n, r += n+1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) res = max(res, st[l++]);
if (r & 1) res = max(res, st[--r]);
}
return res;
}
} st2;
int N, X[MAX], Y[MAX];
set<int, greater<int>> non_one; // position of non-one numbers
int calc()
{
vector<int> idx = { N };
{
ll val = 1;
for (int x : non_one)
{
idx.pb(x);
val *= X[x];
if (val > inf)
break;
}
if (val <= inf && idx.back() != 0)
idx.pb(0);
}
reverse(idx.begin(), idx.end());
ll mx = 0; int best = 0, ybest = 0;
for (int i = 0; i+1 < (int)idx.size(); ++i)
{
int ymax = st2.query(idx[i], idx[i+1] - 1);
ll xval = st1.query(idx[1], idx[i]).val;
// cerr << idx[i] << " " << idx[i+1] << " " << xval << " " << ymax << '\n';
if (ymax * xval > mx)
mx = ymax * xval, best = i, ybest = ymax;
}
// cerr << "best: " << best << '\n';
// cerr << '\n';
return (st1.query(0, idx[best]) * ybest).val;
}
int init(int n, int x[], int y[])
{
N = n;
for (int i = 0; i < N; ++i)
X[i] = x[i], Y[i] = y[i];
st1 = Segtree1(n, x);
st2 = Segtree2(n, y);
for (int i = 0; i < N; ++i) if (x[i] != 1)
non_one.insert(i);
return calc();
}
int updateX(int pos, int val)
{
st1.modify(pos, val);
if (val == 1) non_one.erase(pos);
else non_one.insert(pos);
return calc();
}
int updateY(int pos, int val)
{
st2.modify(pos, val);
return calc();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
19 ms |
10776 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |