#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz
#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y)
{
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y)
{
x = y;
return true;
}
return false;
}
const int MOD = 1e9 + 7; //998244353
template<class X, class Y>
void add(X &x, const Y &y) {
x = (x + y);
if(x >= MOD) x -= MOD;
}
template<class X, class Y>
void sub(X &x, const Y &y) {
x = (x - y);
if(x < 0) x += MOD;
}
/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
const ll INF = 1e9;
const int N = 1e5 + 10;
template <typename T> T mod_inv_in_range(T a, T m) {
// assert(0 <= a && a < m);
T x = a, y = m;
T vx = 1, vy = 0;
while (x) {
T k = y / x;
y %= x;
vy -= k * vx;
std::swap(x, y);
std::swap(vx, vy);
}
assert(y == 1);
return vy < 0 ? m + vy : vy;
}
template <typename T> T mod_inv(T a, T m) {
a %= m;
a = a < 0 ? a + m : a;
return mod_inv_in_range(a, m);
}
template <int MOD_> struct modnum {
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
using ll = long long;
int v;
public:
modnum() : v(0) {}
modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
explicit operator int() const { return v; }
friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
modnum inv() const {
modnum res;
res.v = mod_inv_in_range(v, MOD);
return res;
}
friend modnum inv(const modnum& m) { return m.inv(); }
modnum neg() const {
modnum res;
res.v = v ? MOD-v : 0;
return res;
}
friend modnum neg(const modnum& m) { return m.neg(); }
modnum operator- () const {
return neg();
}
modnum operator+ () const {
return modnum(*this);
}
modnum& operator ++ () {
v ++;
if (v == MOD) v = 0;
return *this;
}
modnum& operator -- () {
if (v == 0) v = MOD;
v --;
return *this;
}
modnum& operator += (const modnum& o) {
v -= MOD-o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum& operator -= (const modnum& o) {
v -= o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum& operator *= (const modnum& o) {
v = int(ll(v) * ll(o.v) % MOD);
return *this;
}
modnum& operator /= (const modnum& o) {
return *this *= o.inv();
}
friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<MOD>;
template <class T> struct FenwickTree {
int n;
vector<T> bit;
FenwickTree(int _n = 0) {
n = _n;
bit.resize(n + 5);
for(int i = 1; i <= n; i++) bit[i] = 0;
}
void update(int pos, T x) {
for(int i = pos; i <= n; i += i & (-i)) bit[i] += x;
}
T get(int pos) {
T ans = 0;
for(int i = pos; i > 0; i -= i & (-i)) ans += bit[i];
return ans;
}
};
struct SegTree {
int n;
vector<int> node;
SegTree(int _n = 0) {
n = _n;
node.resize(4 * n + 7);
}
private:
void Update(int l, int r, int pos, int val, int id) {
if(l == r) {
node[id] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) Update(l, mid, pos, val, id << 1);
else Update(mid + 1, r, pos, val, id << 1 | 1);
node[id] = max(node[id << 1], node[id << 1 | 1]);
}
int Get(int l, int r, int lo, int hi, int id) {
if(l > hi || r < lo) return 0;
if(lo <= l && r <= hi) return node[id];
int mid = (l + r) >> 1;
int left = Get(l, mid, lo, hi, id << 1);
int right = Get(mid + 1, r, lo, hi, id << 1 | 1);
return max(left, right);
}
public:
void update(int pos, int val) {
Update(1, n, pos, val, 1);
}
int get(int l, int r) {
return Get(1, n, l, r, 1);
}
};
SegTree IT = SegTree(10);
FenwickTree<num> BIT;
set<int> curr;
int x[N], y[N], n;
int calc() {
int pos = n;
auto iter = curr.end(); iter = prev(iter);
ll r = 0;
int ans = 0;
while(true) {
int t = (*iter);
int v = IT.get(t, pos);
if(v > r) {
r = v;
int cc = BIT.get(t).v;
ans = 1ll * cc * v % MOD;
}
pos = t - 1;
r = r * x[(*iter)];
if(r > INF) break;
if(iter == curr.begin()) break;
iter = prev(iter);
}
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = n; i >= 1; i--) {
x[i] = X[i - 1];
y[i] = Y[i - 1];
}
IT = SegTree(n); BIT = FenwickTree<num>(n);
curr.ins(0);
for(int i = 1; i <= n; i++) {
IT.update(i, y[i]);
BIT.update(i, x[i]);
if(x[i] > 1) curr.ins(i);
}
return calc();
}
int updateX(int pos, int val) {
pos++;
if(x[pos] > 1) curr.erase(pos);
BIT.update(pos, num(1) / num(x[pos]));
x[pos] = val;
if(x[pos] > 1) curr.ins(pos);
BIT.update(pos, x[pos]);
return calc();
}
int updateY(int pos, int val) {
++pos;
y[pos] = val;
IT.update(pos, y[pos]);
return calc();
}
Compilation message
horses.cpp: In function 'int calc()':
horses.cpp:249:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
249 | ans = 1ll * cc * v % MOD;
| ~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:262:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
262 | int init(int N, int X[], int Y[]) {
| ~~~~^
horses.cpp:71:11: note: shadowed declaration is here
71 | const int N = 1e5 + 10;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
10444 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
