#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define Tree int h,int l,int r
#define left 2*h,l,(l+r)/2
#define right 2*h+1,(l+r)/2+1,r
#define Pb push_back
#define F first
#define S second
int Inf=1000000008,Mod=1000000007;
int P,n,x[500002],y[500002],ANS;
int Ind,Z;
int v[2000002];
pair < int , int > vy[2000002];
set < int > st;
set <int > :: iterator it;
vector < int > V;
pair < int , int > X;
int L,R;
void Update(Tree)
{
if (l>L || r<L) return ;
if (L==l && r==L) { v[h]=R%Mod; return ; }
Update(left);
Update(right);
v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}
int Get(Tree)
{
if (L>r || l>R) return 1;
if (L<=l && r<=R) return v[h];
return (1LL*Get(left)*Get(right))%Mod;
}
void Upy(Tree)
{
if (l>L || r<L) return ;
if (L==l && r==L) { vy[h].F=R; vy[h].S=L; return ; }
Upy(left);
Upy(right);
if (vy[2*h].F>vy[2*h+1].F) vy[h]=vy[2*h];
else vy[h]=vy[2*h+1];
}
pair < int , int > Gety(Tree)
{
if (L>r || l>R) return make_pair(0,0);
if (L<=l && r<=R) return make_pair(vy[h].F,vy[h].S);
pair < int , int > X1=Gety(left);
pair < int , int > X2=Gety(right);
if (X1.F>X2.F) return X1;
return X2;
}
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];
for (int i=0; i<n; i++)
{
L=i; R=x[i];
Update(0,0,n-1);
if (x[i]>1) st.insert(i);
}
for (int i=0; i<n; i++)
{
L=i; R=y[i];
Upy(0,0,n-1);
}
Ind=1;
P=1;
for (int j=1; j<n; j++)
{
if (1LL*P*x[j]<Inf) P*=x[j];
else P=Inf;
if (y[Ind]<1LL*P*y[j]) P=1,Ind=j;
}
L=0; R=Ind;
ANS=(1LL*Get(0,0,n-1)*y[Ind])%Mod;
return ANS;
}
long long Ann()
{
it=st.end();
V.clear();
Z=0;
while (it!=st.begin())
{
Z++;
it--;
V.Pb((*it));
if (Z>35) break;
}
if (!V.size() || V[V.size()-1]!=0) V.Pb(0);
reverse(V.begin(),V.end());
if (!V.size() || V[V.size()-1]!=n-1) V.Pb(n-1);
Ind=0;
P=1;
for (int i=0; i<V.size(); i++)
{
if (1LL*P*x[V[i]]<Inf) P*=x[V[i]];
else P=Inf;
if (y[Ind]<1LL*P*y[V[i]]) P=1,Ind=V[i];
if (i==V.size()-1) continue;
L=V[i]+1; R=V[i+1]-1;
X=Gety(0,0,n-1);
if (y[Ind]<1LL*P*X.F) P=1,Ind=X.S;
}
L=0; R=Ind;
ANS=(1LL*Get(0,0,n-1)*y[Ind])%Mod;
return ANS;
}
int updateX(int pos, int val) {
if (x[pos]==1 && val>1) st.insert(pos);
else
if (x[pos]>1 && val==1) st.erase(st.find(pos));
x[pos]=val;
Update(0,0,n-1);
return Ann();
}
int updateY(int pos, int val) {
y[pos]=val;
Upy(0,0,n-1);
return Ann();
}
Compilation message
horses.cpp: In function 'void Update(int, int, int)':
horses.cpp:31:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int Get(int, int, int)':
horses.cpp:38:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (1LL*Get(left)*Get(right))%Mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:64:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
int init(int N, int X[], int Y[]) {
^
horses.cpp:20:20: note: shadowed declaration is here
pair < int , int > X;
^
horses.cpp:97:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
ANS=(1LL*Get(0,0,n-1)*y[Ind])%Mod;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'long long int Ann()':
horses.cpp:124:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<V.size(); i++)
~^~~~~~~~~
horses.cpp:131:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i==V.size()-1) continue;
~^~~~~~~~~~~~
horses.cpp:142:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
ANS=(1LL*Get(0,0,n-1)*y[Ind])%Mod;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:157:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return Ann();
~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:165:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return Ann();
~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1202 ms |
42104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
42104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
42104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
