#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nax = 5e5 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9;
long long x[nax], y[nax];
int n;
long long mul(long long a, long long b) {
return (a * b) % mod;
}
long long quickpow(long long a, long long b) {
long long ret = 1;
while(b) {
if(b&1) ret = mul(ret, a);
a = mul(a, a);
b >>= 1;
}
return ret;
}
struct BIT {
long long b[nax];
BIT() {
for(int i=0; i<nax; ++i) {
b[i] = 1;
}
}
void update(int p, int val) {
while(p<nax) {
b[p] = mul(b[p], val);
p += p&-p;
}
}
long long query(int p) {
long long ret = 1;
while(p) {
ret = mul(ret, b[p]);
p -= p&-p;
}
return ret;
}
} fen;
int seg[nax * 4];
void update(int pos, int val, int l=1, int r=n, int v=1) {
if(l==r) {
seg[v] = val;
return;
}
int mid = (l+r)/2;
if(pos<=mid) update(pos, val, l, mid, v*2);
else update(pos, val, mid+1, r, v*2+1);
seg[v] = max(seg[v*2], seg[v*2+1]);
}
int query(int L, int R, int l=1, int r=n, int v=1) {
if(l>=L && r<=R) return seg[v];
if(l>R || r<L) return 0;
int mid = (l+r)/2;
return max(query(L, R, l, mid, v*2), query(L, R, mid+1, r, v*2+1));
}
set<int>nonone;
long long get_ans(int day) {
int sell_max_day;
auto it = nonone.upper_bound(day);
if(it==nonone.end()) {
sell_max_day = n-1;
} else {
sell_max_day = *it-1;
}
long long price = query(day+1, sell_max_day+1);
long long cnt = 1;
bool better = 0;
for(; it!=nonone.end(); ++it) {
cnt *= x[*it];
int then_sell_max_day;
if(next(it)==nonone.end()) {
then_sell_max_day = n-1;
} else {
then_sell_max_day = *next(it) - 1;
}
long long then_price = query(*it+1, then_sell_max_day+1);
if(cnt * then_price > price) {
better = true;
}
if(cnt>MX) {
better = true;
}
}
if(better) return -1;
return price * fen.query(day+1);
}
int get() {
auto it = nonone.end();
int iter = 30;
while(iter--) {
if(it!=nonone.begin()) --it;
}
if(it==nonone.begin()) {
long long ans = get_ans(0);
if(ans!=-1) return ans;
}
while(it!=nonone.end()) {
long long ans = get_ans(*it);
if(ans!=-1) return ans;
}
}
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];
fen.update(i+1, x[i]);
update(i+1, y[i]);
if(x[i]>1) nonone.insert(i);
}
return get();
}
int updateX(int pos, int val) {
fen.update(pos+1, quickpow(x[pos], mod-2));
fen.update(pos+1, val);
if(x[pos]==1 && val>1) {
nonone.insert(pos);
} else if(x[pos]>1 && val==1) {
nonone.erase(pos);
}
x[pos] = val;
get();
}
int updateY(int pos, int val) {
update(pos+1, val);
y[pos] = val;
get();
}
Compilation message
horses.cpp: In function 'int get()':
horses.cpp:114:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
114 | if(ans!=-1) return ans;
| ^~~
horses.cpp:118:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
118 | if(ans!=-1) return ans;
| ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:125:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
125 | fen.update(i+1, x[i]);
| ~~~^
horses.cpp:126:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
126 | update(i+1, y[i]);
| ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:134:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
134 | fen.update(pos+1, quickpow(x[pos], mod-2));
| ~~~~~~~~^~~~~~~~~~~~~~~
horses.cpp:146:1: warning: no return statement in function returning non-void [-Wreturn-type]
146 | }
| ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:153:1: warning: no return statement in function returning non-void [-Wreturn-type]
153 | }
| ^
horses.cpp: In function 'int get()':
horses.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
120 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4180 KB |
Output is correct |
| 2 |
Execution timed out |
1582 ms |
4232 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Execution timed out |
1579 ms |
4228 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1545 ms |
45624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Execution timed out |
1567 ms |
4180 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4228 KB |
Output is correct |
| 2 |
Execution timed out |
1575 ms |
4228 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
