This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define ld double
#define F first
#define S second
#define lc id*2+1
#define rc id*2+2
using namespace std;
const ll p=1e9+7;
ll pw(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans*=a,ans%=p;
b>>=1,a*=a,a%=p;
}
return ans;
}
ll x[500010],y[500010],n;
struct BIT{
ll ori[500010];
void init(){
for(int i=0;i<=n;i++)ori[i]=1;
return;
}
void modify(ll x,int pos){
while(pos<=n){
ori[pos]*=x;
ori[pos]%=p;
pos+=pos&(-pos);
}
return;
}
ll query(ll pos){
ll ans=1;
while(pos){
ans*=ori[pos];
ans%=p;
pos-=pos&(-pos);
}
return ans;
}
}bit;
struct SEG_TREE{
pair<int,int> ori[2000010];
void build(int l,int r,int id){
if(l==r){
ori[id]={y[l],l};
return;
}
int m=(l+r)>>1;
build(l,m,lc);
build(m+1,r,rc);
ori[id]=max(ori[lc],ori[rc]);
return;
}
void modify(int l,int r,int pos,int id,int x){
if(l==pos&&r==pos){
ori[id]={x,l};
return;
}
int m=(l+r)>>1;
if(pos<=m){
modify(l,m,pos,lc,x);
}else{
modify(m+1,r,pos,rc,x);
}
ori[id]=max(ori[lc],ori[rc]);
return;
}
pair<int,int> query(int l,int r,int ql,int qr,int id){
if(l==ql&&r==qr){
return ori[id];
}
int m=(l+r)>>1;
if(qr<=m){
return query(l,m,ql,qr,lc);
}else if(m<ql){
return query(m+1,r,ql,qr,rc);
}else{
return max(query(l,m,ql,m,lc),query(m+1,r,m+1,qr,rc));
}
}
}seg;
set<int> big;
ll q(){
if(big.size()==1){
return seg.query(1,n,1,n,0).F;
}
set<int>::iterator k=(--(--big.end()));
ll pos=0;
int now=0;
ld nw=0,maxn=0;
while(now<50&&k!=big.begin()){
assert(x[*k]>1);
now++;
k--;
}
while(k!=(--big.end())){
nw+=log2(x[*k]);
//cout<<*k<<" "<<*(nx)<<"\n";
pair<int,int> pp=seg.query(1,n,*k,n,0);
//cout<<pp.F<<" "<<pp.S<<"\n";
if(maxn<nw+log2(pp.F)){
maxn=nw+log2(pp.F);
pos=pp.S;
}
++k;
}
ll a=bit.query(pos);
//cout<<a<<"?\n";
a*=y[pos];
//cout<<a<<" 888\n";
a%=p;
//cout<<pos<<"\n";
return a;
}
int init(int N, int X[], int Y[]) {
n=N;
big.insert(n+1);
bit.init();
for(int i=0;i<n;i++){
x[i+1]=X[i];
bit.modify(x[i+1],i+1);
if(x[i+1]>1)big.insert(i+1);
y[i+1]=Y[i];
}
seg.build(1,n,0);
return q();
}
int updateX(int pos, int val) {
pos+=1;
bit.modify((pw(x[pos],p-2)*val)%p,pos);
x[pos]=val;
if(val==1)big.erase(pos);
else big.insert(pos);
return q();
}
int updateY(int pos, int val) {
pos+=1;
seg.modify(1,n,pos,0,val);
y[pos]=val;
return q();
}
Compilation message (stderr)
horses.cpp: In member function 'void BIT::modify(long long int, int)':
horses.cpp:26:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
26 | void modify(ll x,int pos){
| ^
horses.cpp:19:4: note: shadowed declaration is here
19 | ll x[500010],y[500010],n;
| ^
horses.cpp: In member function 'void SEG_TREE::modify(int, int, int, int, int)':
horses.cpp:57:45: warning: declaration of 'x' shadows a global declaration [-Wshadow]
57 | void modify(int l,int r,int pos,int id,int x){
| ~~~~^
horses.cpp:19:4: note: shadowed declaration is here
19 | ll x[500010],y[500010],n;
| ^
horses.cpp: In function 'long long int q()':
horses.cpp:90:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | return seg.query(1,n,1,n,0).F;
| ^
horses.cpp:90:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | return seg.query(1,n,1,n,0).F;
| ^
horses.cpp:104:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
104 | pair<int,int> pp=seg.query(1,n,*k,n,0);
| ^
horses.cpp:104:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
104 | pair<int,int> pp=seg.query(1,n,*k,n,0);
| ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:123:14: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
123 | big.insert(n+1);
| ~^~
horses.cpp:131:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
131 | seg.build(1,n,0);
| ^
horses.cpp:132:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
132 | return q();
| ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:141:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
141 | return q();
| ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
146 | seg.modify(1,n,pos,0,val);
| ^
horses.cpp:148:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
148 | return q();
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |