#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long mod = 1e9 + 7;
struct range {
public:
ll p_m, s_m, m_m, h_a;
int p_o, s_o, x, y;
range()
{
h_a = 1;
p_m = s_m = m_m = 1;
p_o = s_o = x = y = 0;
}
range(int i_, int x_, int y_)
{
h_a = 1;
s_m = 1;
p_m = x_;
x = x_;
y = y_;
m_m = y_;
p_o = s_o = 0;
}
range operator+(range b)
{
range res;
bool choose = false;
if (s_m * b.p_m > mod)
choose = true;
else if (s_m * b.p_m * b.m_m > m_m)
choose = true;
if (s_o || b.s_o)
choose = true;
if (choose) {
res.p_m = b.p_m * s_m;
int tp_o = 0;
if (res.p_m >= mod)
tp_o = 1;
res.p_m %= mod;
res.h_a *= res.p_m;
res.h_a %= mod;
res.p_m *= p_m;
if (res.p_m >= mod)
tp_o = 1;
res.p_m %= mod;
res.p_o = p_o | tp_o;
res.m_m = b.m_m;
res.s_m = b.s_m;
res.s_o = b.s_o;
} else {
res.s_m = b.s_m * s_m;
int ts_o = 0;
if (res.s_m >= mod)
ts_o = 1;
res.s_m %= mod;
res.s_m *= b.p_m;
if (res.s_m >= mod)
ts_o = 1;
res.s_m %= mod;
res.s_o = b.s_o | ts_o;
res.p_m = p_m;
res.p_o = p_o;
res.m_m = m_m;
res.h_a = h_a;
}
return res;
}
};
template <class T>
struct SegTree {
int n;
vector<T> v;
void rupdate(int i, int l, int r, int idx, T val)
{
if (r - l == 1) {
if (l == idx)
v[i] = val;
} else {
int m = (r - l) / 2 + l;
if (idx < m)
rupdate(2 * i, l, m, idx, val);
else
rupdate(2 * i + 1, m, r, idx, val);
v[i] = v[2 * i] + v[2 * i + 1];
}
}
void update(int idx, T val)
{
rupdate(1, 0, n, idx, val);
}
T query()
{
return v[1];
}
SegTree() { }
SegTree(vector<T> in)
{
n = 1;
while (n < in.size())
n *= 2;
v = vector<T>(2 * n + 5);
for (int i = 0; i < in.size(); i++)
update(i, in[i]);
}
};
SegTree<range> st;
vector<range> vr;
int init(int N, int X[], int Y[])
{
vr = vector<range>(N);
for (int i = 0; i < N; i++) {
vr[i] = range(i, X[i], Y[i]);
}
//cout << N << endl;
st = SegTree<range>(vr);
return (st.query().h_a * st.query().m_m) % mod;
}
int updateX(int pos, int val)
{
vr[pos] = range(pos, val, vr[pos].y);
st.update(pos, vr[pos]);
return (st.query().h_a * st.query().m_m) % mod;
}
int updateY(int pos, int val)
{
vr[pos] = range(pos, vr[pos].x, val);
st.update(pos, vr[pos]);
return (st.query().h_a * st.query().m_m) % mod;
}
Compilation message
horses.cpp: In constructor 'range::range(int, int, int)':
horses.cpp:19:15: warning: unused parameter 'i_' [-Wunused-parameter]
19 | range(int i_, int x_, int y_)
| ~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:124:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
124 | return (st.query().h_a * st.query().m_m) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:131:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
131 | return (st.query().h_a * st.query().m_m) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
138 | return (st.query().h_a * st.query().m_m) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In instantiation of 'SegTree<T>::SegTree(std::vector<_Tp>) [with T = range]':
horses.cpp:123:27: required from here
horses.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range, std::allocator<range> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while (n < in.size())
| ~~^~~~~~~~~~~
horses.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range, std::allocator<range> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int i = 0; i < in.size(); i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
287 ms |
100388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
