#include "horses.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef set<ll> sll;
const ll modulo = 1000000007; // prime
const bool debug = false;
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define rrep(a,b,c) for(ll a=c-1; a>=b; a--)
#define itr_rep(a,b,_type) for(_type::iterator a=b.begin(); a!=b.end(); a++)
#define ritr_rep(a,b,_type) for(_type::reverse_iterator a=b.rbegin(); a!=b.rend(); a++)
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
#define pb(a) push_back(a)
#define db(x) if(debug){cout << x << endl;}
ll inverse(ll num); // mul inv mod modulo
ll find_max();
//int updateX(int pos, int val);
//int updateY(int pos, int val);
void Build();
ll query(ll v, ll vl, ll vr, ll l, ll r);
void update(ll v, ll vl, ll vr, ll pos, ll val);
ll n;
ll m;
sll non_one;
ll prod;
vll x;
vll y;
vll x_inv;
vll y_op;
vll seg;
int init(int N, int X[], int Y[]) {
prod = 1;
n = (ll)N;
x.resize(n,0);
y.resize(n,0);
x_inv.resize(n,0);
y_op.resize(n,0);
non_one.clear();
rep(i,0,n) {x[i] = (ll)X[i];}
rep(i,0,n) {y[i] = (ll)Y[i];}
rep(i,0,n) {
if (x[i] != 1) {
non_one.insert(i); // nlogn but whatever.
}
}
rep(i,0,n) {
x_inv[i] = inverse(x[i]); // nlogn. eh
prod = (prod*x[i]) % modulo;
}
// segtree time
Build();
db("build done");
non_one.insert(n); // for the benefit of the first element due to prev...
for(sll::iterator itr = non_one.begin(); next(itr) != non_one.end(); itr++) {
db(*itr);
y_op[*itr] = query(1, 0, n-1, (*itr), (*next(itr))-1);
}
db("segtree done");
if (debug) {
rep(i,0,n) {cout << y_op[i] << " ";}
cout << endl;
rep(i,0,seg.size()) {cout << seg[i] << " ";}
cout << endl;
}
return (int)find_max();
//cout << find_max() << endl;
/*ll val;
ll pos;
cin >> m;
rep(i,0,m) {
cin >> pos;
cin >> val;
cout << updateY(pos,val) << endl;
//continue; // do things
}
if (debug) {
rep(i,0,n) {cout << y_op[i] << " ";}
cout << endl;
rep(i,0,seg.size()) {cout << seg[i] << " ";}
cout << endl;
}*/
//rep(i,0,n) {cout << x[i] << " " << x_inv[i] << " " << y[i] << endl;}
}
int updateX(int pos, int val) {
if (val != 1) {
if (x[pos] == 1) {
sll::iterator itr = (non_one.insert(pos)).first;
y_op[pos] = query(1,0,n-1,*itr,(*next(itr))-1);
if (itr != non_one.begin()) {
y_op[*prev(itr)] = query(1,0,n-1,*prev(itr),(*itr)-1);
}
}
} else if (x[pos] != 1) {
sll::iterator itr = non_one.erase(non_one.find(pos)); // gets the element after. Need the one before
if (itr != non_one.begin()) {
y_op[*prev(itr)] = query(1,0,n-1,*prev(itr),(*itr)-1);
}
}
prod = (prod*x_inv[pos]) % modulo;
prod = (prod*val) % modulo;
x[pos] = val;
x_inv[pos] = inverse(val);
return (int)find_max();
}
int updateY(int pos, int val) { // bruh
y[pos] = val;
update(1,0,n-1,pos,val);
sll::iterator itr = non_one.upper_bound(pos); // exclusive range -> when prev -> inclusive downwards xdddddddddd
if (itr != non_one.begin()) {
y_op[*prev(itr)] = query(1,0,n-1,*prev(itr),(*itr)-1);
}
return (int)find_max();
}
ll inverse(ll num) { // modulo modulo - haha code it myself bc practice not perform nvm wikipedia it is
ll old_r = modulo;
ll r = num;
//ll old_s = 1;
//ll s = 0;
ll old_t = 0;
ll t = 1;
ll q;
while (r > 0) {
q = old_r / r;
old_r -= q*r;
swap(r,old_r);
//old_s -= q*s;
//swap(s,old_s);
old_t -= q*t;
swap(t,old_t);
}
return (old_t + modulo) % modulo;
}
ll find_max() { // assume we have already updated
ll best = 1; //
ll new_prod = prod;
for(sll::reverse_iterator itr = next(non_one.rbegin()); itr != non_one.rend(); itr++) {
if (y_op[*itr] > best) {
best = y_op[*itr];
}
new_prod = (new_prod*x_inv[*itr]) % modulo;
best = best*x[*itr];
db("b");
db(*itr);
db(x[*itr]);
db(best);
if (best > 1000000000) {return (best*new_prod) % modulo;}
}
best = max(best, query(1,0,n-1,0,(*non_one.begin())-1)); // For the "trailing" 1s at the beginning
return (best*new_prod) % modulo;
}
void Build() {
ll s = 1;
for(ll i = n-1; i>0; i>>=1) {s <<= 1;}
//cout << s << endl;
seg.resize(2*s,0);
rep(i,0,n) {seg[s+i] = y[i];}
rep(i,1,s+1) {seg[s-i] = max(seg[2*s - 2*i], seg[2*s - 2*i + 1]);}
}
ll query(ll v, ll vl, ll vr, ll l, ll r) {
if (l>r) {return 0;}
if ((l==vl) && (r==vr)) {return seg[v];}
ll vm = (vl+vr)/2;
return max(query(2*v,vl,vm,l,min(r,vm)),query(2*v+1,vm+1,vr,max(l,vm+1),r));
}
void update(ll v, ll vl, ll vr, ll pos, ll val) {
if (vl==vr) {seg[v]=val;}
else {
ll vm = (vl+vr)/2;
if (pos <= vm) {update(2*v,vl,vm,pos,val);}
else {update(2*v+1,vm+1,vr,pos,val);}
seg[v] = max(seg[2*v],seg[2*v+1]);
}
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:15:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | #define rep(a,b,c) for(ll a=b; a<c; a++)
......
74 | rep(i,0,seg.size()) {cout << seg[i] << " ";}
| ~~~~~~~~~~~~~~
horses.cpp:74:9: note: in expansion of macro 'rep'
74 | rep(i,0,seg.size()) {cout << seg[i] << " ";}
| ^~~
| # |
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 |
248 ms |
52536 KB |
Output is correct |
| 2 |
Incorrect |
320 ms |
52552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
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 |
- |
