| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 824978 |
2023-08-14T12:47:44 Z |
Nelt |
Horses (IOI15_horses) |
C++17 |
|
48 ms |
24788 KB |
#include "horses.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define ANDROID \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 5e5 + 5, mod = 1e9 + 7;
ll a[N], b[N], n;
ll t[N];
ll binpow(ll n, ll p)
{
ll ans = 1;
n %= mod;
while (p)
{
ans = (p & 1 ? (ans * n) % mod : ans);
n = (n * n) % mod;
p >>= 1;
}
return ans;
}
ll inv(ll x)
{
return binpow(x, mod - 2);
}
ll product(ll i)
{
ll res = 1;
for (; i > 0; i = (i & (i + 1)) - 1)
res = res * t[i] % mod;
return res;
}
void upd(ll i, ll d)
{
for (; i <= n; i = (i | (i + 1)))
t[i] = t[i] * d % mod;
}
struct SegTree
{
ll n;
vv(ll) st;
SegTree(ll sz = 0, bool input = false)
{
n = sz;
st.resize((n + 1) << 1, 0);
}
void set(ll i, ll val)
{
st[i + n - 1] = val;
}
void build()
{
for (ll i = n - 1; i >= 1; i--)
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
void modify(ll p, ll val)
{
for (st[p += n - 1] = val; p > 1; p >>= 1)
st[p >> 1] = max(st[p], st[p ^ 1]);
}
ll query(ll l, ll r)
{
ll ans = 0;
for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, st[l++]);
if (r & 1)
ans = max(ans, st[--r]);
}
return ans;
}
} st(N);
ss(ll) s;
ll solve()
{
ll prod = 1;
auto it = --s.end();
while (it != s.begin() and prod * a[*it] <= 1e9)
prod *= a[*it], it--;
prod = 1;
ll ans = st.query(1, *s.begin() - 1), start = *it;
for (; *it != n + 1; it++)
prod *= a[*it], ans = max(ans, prod * st.query(*it, *next(it) - 1));
return ans % mod * product(start - 1) % mod;
}
int init(int N, int X[], int Y[])
{
n = N;
for (ll i = 0; i < n; i++)
a[i + 1] = X[i], b[i + 1] = Y[i], t[i + 1] = 1;
for (ll i = 1; i <= n; i++)
{
if (a[i] > 1)
s.ins(a[i]);
st.set(i, b[i]);
upd(i, a[i]);
}
st.build();
a[n + 1] = b[n + 1] = 1;
s.ins(n + 1);
return solve();
}
int updateX(int pos, int val)
{
pos++;
upd(pos, val * inv(a[pos]) % mod);
a[pos] = val;
if (a[pos] > 1)
s.ins(pos);
elif (s.count(pos))
s.erase(pos);
return solve();
}
int updateY(int pos, int val)
{
pos++;
st.modify(pos, b[pos] = val);
return solve();
}
Compilation message
horses.cpp: In function 'long long int binpow(long long int, long long int)':
horses.cpp:48:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
48 | ll binpow(ll n, ll p)
| ^
horses.cpp:46:16: note: shadowed declaration is here
46 | ll a[N], b[N], n;
| ^
horses.cpp: In constructor 'SegTree::SegTree(long long int, bool)':
horses.cpp:80:29: warning: unused parameter 'input' [-Wunused-parameter]
80 | SegTree(ll sz = 0, bool input = false)
| ~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:117:37: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
117 | while (it != s.begin() and prod * a[*it] <= 1e9)
| ~~~~~^~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:125:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
125 | int init(int N, int X[], int Y[])
| ~~~~^
horses.cpp:45:10: note: shadowed declaration is here
45 | const ll N = 5e5 + 5, mod = 1e9 + 7;
| ^
horses.cpp:140:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
140 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:152:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
152 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:158:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
158 | return solve();
| ~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
8156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
24788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
