#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
int n;
set<int> good;
int startpos = -1;
int sgmax[2*mxN];
ll ans = 1;
ll x[mxN];
int y[mxN];
void build() {
for(int i=n; i<2*n; ++i) sgmax[i] = y[i-n];
for(int i=n-1; i>0; --i) sgmax[i] = max(sgmax[i<<1], sgmax[i<<1|1]);
}
void upd(int p, int val) {
for(sgmax[p+=n] =val; p>0; p>>=1) sgmax[p>>1] = max(sgmax[p], sgmax[p^1]);
}
int qmax(int l, int r) {
r++;
int res = 0;
for(l+=n, r+=n; l<r; l>>=1, r>>=1) {
if(l&1)res = max(res, sgmax[l++]);
if(r&1)res = max(res, sgmax[--r]);
}
return res;
}
ll binpow(ll a, ll b) { ll res = 1; while(b){ if(b&1) res = (res*a)%MOD; b>>=1; a = (a*a)%MOD;}return res;}
ll modInv(ll a) {return binpow(a, MOD-2);}
ll solve() {
if(startpos==-1) return qmax(0, n-1);
ll best= 1;
ll curr = 1;
ll partans = 1;
int start = startpos;
auto it = --good.end();
while(partans<(ll)(1e9+7)&&start>startpos) {
partans*=x[*it];
start = *it;
if(it==good.begin())break;
it--;
}
partans = 1;
owo(i, startpos, start){
partans = partans*x[i]%MOD;
}
it = good.lower_bound(start);
while(it!=good.end()) {
curr = curr*(x[*it]);
best = max(best, (ll)qmax(*it, next(it)==good.end() ? n-1 : *next(it))*curr);
it++;
}
return ((ans*partans)%MOD*best%MOD);
}
ll init(int N, int X[], int Y[]) {
n = N;
owo(i, 0, mxN) {
x[i] = X[i];
y[i] = Y[i];
}
build();
owo(i, 0, n) {
if(x[i]>1) good.insert(i);
}
auto it = --good.end();
int num = 60;
while(num) {
num--;
if(it==good.begin())break;
it--;
}
startpos = *it;
owo(i, 0, startpos) {
ans = (ans*x[i])%MOD;
}
return solve();
}
ll updateX(int pos, int val) {
if(x[pos]==1&&val!=1) {
good.insert(pos);
if(pos<startpos) {
ans = (ans*val)%MOD;
}else if(pos>startpos){
ans = (ans*x[startpos]%MOD);
auto it = good.upper_bound(startpos);
startpos = (it==good.end() ? -1 : *it);
}
//cout<<ans<<" "<<startpos<<"\n";
}else if(x[pos]!=1&&val==1) {
auto it = good.find(pos);
if(pos<startpos) {
ans = (ans*modInv(x[pos]))%MOD;
}else if(pos>=startpos) {
if(it!=good.begin()) {
startpos = *prev(it);
}
}
good.erase(good.find(pos));
}else if(x[pos]!=1) {
if(pos<startpos) {
ans = (ans*modInv(x[pos]))%MOD;
ans = (ans*val)%MOD;
}
}
x[pos] = val;
return solve();
}
ll updateY(int pos, int val) {
upd(pos, val);
return solve();
}
/*int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
int tempn;
int tempx[mxN];
int tempy[mxN];
cin>>tempn;
owo(i, 0, tempn) {
cin>>tempx[i];
}
owo(i,0, tempn) {
cin>>tempy[i];
}
cout<<init(tempn, tempx, tempy)<<"\n";
int q;
int a, b;
cin>>q;
while(q--) {
cin>>a>>b;
cout<<updateX(a, b)<<"\n";
}
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
38648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
