#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
set <pair <int, int>> s;
int n,st[2000001][2],x[500001],y[500001],mx[500001];
void build(int node, int l, int r){
if (l==r){
st[node][0]=x[l];
st[node][1]=y[l];
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
st[node][1]=max(st[node<<1][1],st[node<<1|1][1]);
}
void update(int node, int l, int r, int i, int val, int id){
if (l>i||r<i)
return;
if (l==r){
st[node][id]=val;
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,i,val,id);
update(node<<1|1,mid+1,r,i,val,id);
st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
st[node][1]=max(st[node<<1][1],st[node<<1|1][1]);
}
int getprod(int node, int l, int r, int u, int v){
if (l>v||r<u||l>r||u>v)
return 1;
if (l>=u&&r<=v)
return st[node][0];
int mid=(l+r)>>1;
return 1LL*getprod(node<<1,l,mid,u,v)*getprod(node<<1|1,mid+1,r,u,v)%mod;
}
int getmax(int node, int l, int r, int u, int v){
if (l>v||r<u||l>r||u>v)
return 1;
if (l>=u&&r<=v)
return st[node][1];
int mid=(l+r)>>1;
return max(getmax(node<<1,l,mid,u,v),getmax(node<<1|1,mid+1,r,u,v));
}
void add(int i){
if (s.empty()){
s.insert({0,st[1][1]});
return;
}
auto it=s.upper_bound(make_pair(i,0));
int val=getmax(1,0,n-1,i,(it==s.end()?n:(*it).first-1));
mx[i]=val;
if (it!=s.begin()){
it--;
auto p=*it;
s.erase(it);
p.second=getmax(1,0,n-1,p.first,i-1);
mx[p.first]=p.second;
s.insert(p);
}
s.insert({i,val});
}
void del(int i){
if (!i)
return;
auto it=s.find({i,mx[i]});
int r=n;
if (it!=s.end()){
it++;
r=(*it).first-1;
it--;
}
if (it!=s.begin()){
it--;
auto p=*it;
s.erase(it);
p.second=getmax(1,0,n-1,p.first,r);
mx[p.first]=p.second;
s.insert(p);
}
s.erase({i,mx[i]});
}
int calc(){
auto it=--s.end();
for (int i=0;i<31;i++){
if (it==s.begin())
break;
it--;
}
auto res=*it;
int cur=1;
it++;
while (it!=s.end()){
auto p=*it;
if (x[p.first]>res.first/cur){
res=p;
cur=1;
it++;
continue;
}
cur*=x[p.first];
if (p.second>res.first/cur){
res=p;
cur=1;
it++;
continue;
}
cur*=p.second;
it++;
}
return 1LL*getprod(1,0,n-1,0,res.first)*res.second%mod;
}
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];
}
build(1,0,n-1);
for (int i=0;i<n;i++)
if (!i||x[i]>1)
add(i);
return 0;
}
int updateX(int pos, int val){
update(1,0,n-1,pos,val,0);
if (x[pos]==1&&val>1)
add(pos);
if (x[pos]>1&&val==1)
del(pos);
return calc();
}
int updateY(int pos, int val){
update(1,0,n-1,pos,val,1);
return calc();
}
Compilation message
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:16:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
16 | st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void update(int, int, int, int, int, int)':
horses.cpp:29:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
29 | st[node][0]=1LL*st[node<<1][0]*st[node<<1|1][0]%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int getprod(int, int, int, int, int)':
horses.cpp:38:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
38 | return 1LL*getprod(node<<1,l,mid,u,v)*getprod(node<<1|1,mid+1,r,u,v)%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int calc()':
horses.cpp:114:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
114 | return 1LL*getprod(1,0,n-1,0,res.first)*res.second%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:123:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
123 | for (int i=0;i<n;i++)
| ^~~
horses.cpp:126:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
126 | return 0;
| ^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:132:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
132 | if (x[pos]>1&&val==1)
| ^~
horses.cpp:134:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
134 | return calc();
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
430 ms |
47160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
