#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
/*
V[h] - Index;
//Suf[h] - Product from P to Mid;
//Pre[h] - Product from Mid+1 Q-1;
*/
#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 Mp make_pair
#define F first
#define S second
long long Inf=1000000008,Mod=1000000007;
int n,x[500002],y[500002],ANS;
int v[2000002];
int V[2000002];
int Suf[2000002];
int Pre[2000002];
int L,R,typ;
int Pro(Tree)
{
if (L>r || l>R) return 1;
if (L<=l && r<=R) return v[h];
return (1LL*Pro(left)*Pro(right))%Mod;
}
void UpPro(Tree)
{
if (l>L || r<L) return ;
if (L==l && r==L) { v[h]=R%Mod; return ; }
UpPro(left);
UpPro(right);
v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}
void Upd(Tree)
{
if (L>r || L<l) return ;
if (L==l && L==r)
{
V[h]=L;
Pre[h]=R;
Suf[h]=1;
return ;
}
Upd(left);
Upd(right);
if (y[V[2*h]]<1LL*min(Inf,1LL*Suf[2*h]*Pre[2*h+1])*y[V[2*h+1]])
{
V[h]=V[2*h+1];
Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],Inf)*Pre[2*h+1],Inf);
Suf[h]=Suf[2*h+1];
}
else
{
V[h]=V[2*h];
Pre[h]=Pre[2*h];
Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],Inf)*Suf[2*h],Inf);
}
}
pair < int , pair < int , int > > Get(Tree)
{
if (L>r || l>R) return Mp(0,Mp(1,1));
if (L<=l && r<=R) return Mp(V[h],Mp(Pre[h],Suf[h]));
pair < int , pair < int , int > > X1=Get(left);
pair < int , pair < int , int > > X2=Get(right);
if (y[X1.F]<min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,Inf),Inf))
return Mp(X2.F,Mp(min(1LL*min(1LL*X1.S.F*X1.S.S,Inf)*X2.S.F,Inf),X2.S.S));
if (y[X1.F]>=min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,Inf),Inf))
return Mp(X1.F,Mp(X1.S.F,min(1LL*min(1LL*X2.S.F*X2.S.S,Inf)*X1.S.S,Inf)));
}
int init(int N, int X[], int Y[]) {
n=N;
for (int i=1; i<=n; i++)
x[i]=X[i-1],y[i]=Y[i-1];
for (int i=1; i<=n; i++) {
L=i; R=x[i]; typ=1;
Upd(1,1,n);
}
for (int i=1; i<=n; i++) {
L=i; R=y[i]; typ=2;
Upd(1,1,n);
}
L=1; R=Get(1,1,n).F;
return (Pro(1,1,n)*y[R])%Mod;
}
int updateX(int pos, int val) {
pos++;
L=pos; R=val; typ=1;
x[pos]=val;
Upd(1,1,n);
UpPro(1,1,n);
L=1; R=Get(1,1,n).F;
return (Pro(1,1,n)*y[R])%Mod;
}
int updateY(int pos, int val) {
pos++;
L=pos; R=val; typ=2;
y[pos]=val;
Upd(1,1,n);
L=1; R=Get(1,1,n).F;
return (Pro(1,1,n)*y[R])%Mod;
}
Compilation message
horses.cpp: In function 'int Pro(int, int, int)':
horses.cpp:35:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (1LL*Pro(left)*Pro(right))%Mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void UpPro(int, int, int)':
horses.cpp:41:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if (L==l && r==L) { v[h]=R%Mod; return ; }
~^~~~
horses.cpp:46: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 'void Upd(int, int, int)':
horses.cpp:66:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],Inf)*Pre[2*h+1],Inf);
~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:73:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],Inf)*Suf[2*h],Inf);
~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (Pro(1,1,n)*y[R])%Mod;
~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:127:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (Pro(1,1,n)*y[R])%Mod;
~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:141:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (Pro(1,1,n)*y[R])%Mod;
~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'std::pair<int, std::pair<int, int> > Get(int, int, int)':
horses.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
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 |
388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
338 ms |
22448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
22448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
22448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
