#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 500015
#define mod 1000000007
using namespace std;
int dx[MAXN],dy[MAXN],n;
int fast_pow(int a,int b){
int ans=1;
while (b){
if (b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
struct segtree{
ll pos[4*MAXN],val[4*MAXN],val_x[4*MAXN],fac[4*MAXN];
pii remain[4*MAXN];
ll get_val(ll a=1,ll b=1,ll c=1,ll d=1){
vector<ll>vt={a,b,c,d};
ll ans=1;
for (ll i:vt){
ans=ans*i;
if (ans>1e9) return 1e9+2;
}
return ans;
}
void pull(int i){
fac[i]=fac[2*i]*fac[2*i+1]%mod;
if (get_val(remain[2*i].y,remain[2*i+1].x,val[2*i+1])>val[2*i]){
pos[i]=pos[2*i+1]; val[i]=val[2*i+1]; remain[i].y=remain[2*i+1].y; val_x[i]=val_x[2*i+1];
remain[i].x=get_val(remain[2*i].x,remain[2*i].y,val_x[2*i],remain[2*i+1].x);
}
else {
pos[i]=pos[2*i]; val[i]=val[2*i]; remain[i].x=remain[2*i].x; val_x[i]=val_x[2*i];
remain[i].y=get_val(remain[2*i].y,remain[2*i+1].x,remain[2*i+1].y,val_x[2*i+1]);
}
}
void build(int l,int r,int i){
if (l==r){
remain[i]={1,1};
pos[i]=l; val[i]=dy[l]; fac[i]=dx[l]; val_x[i]=dx[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,2*i);
build(mid+1,r,2*i+1);
pull(i);
}
void modify_Y(int l,int r,int i,int p,ll c){
if (l==r){
val[i]=val[i]*c%mod;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify_Y(l,mid,2*i,p,c);
else modify_Y(mid+1,r,2*i+1,p,c);
pull(i);
}
void modify_X(int l,int r,int i,int p,ll c){
if (l==r){
fac[i]=fac[i]*c%mod;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify_X(l,mid,2*i,p,c);
else modify_X(mid+1,r,2*i+1,p,c);
pull(i);
}
ll query(int l,int r,int i,int ql,int qr){
if (ql<=l&&qr>=r) return fac[i];
int mid=(l+r)>>1;
if (qr<=mid) return query(l,mid,2*i,ql,qr);
else if (ql>mid) return query(mid+1,r,2*i+1,ql,qr);
else return query(l,mid,2*i,ql,qr)*query(mid+1,r,2*i+1,ql,qr)%mod;
}
void debug(int l,int r,int i){
cout<<l<<" ~ "<<r<<" : "<<fac[i]<<" best "<<pos[i]<<","<<val[i]<<","<<val_x[i]<<" remain : "<<remain[i].x<<' '<<remain[i].y<<'\n';
if (l==r) return;
int mid=(l+r)>>1;
debug(l,mid,2*i);
debug(mid+1,r,2*i+1);
}
}seg;
int init(int N, int X[], int Y[]) {
n=N;
for (int i=1;i<=n;i++){
dx[i]=X[i-1]; dy[i]=Y[i-1];
}
seg.build(1,n,1);
int best=seg.pos[1];
int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
return ans;
}
int updateX(int pos, int val) {
pos++;
int inv=fast_pow(dx[pos],mod-2);
dx[pos]=val;
seg.modify_X(1,n,1,pos,inv);
seg.modify_X(1,n,1,pos,val);
int best=seg.pos[1];
int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
return ans;
}
int updateY(int pos, int val) {
pos++;
int inv=fast_pow(dy[pos],mod-2);
dy[pos]=val;
seg.modify_Y(1,n,1,pos,inv);
seg.modify_Y(1,n,1,pos,val);
int best=seg.pos[1];
int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
return ans;
}
Compilation message
horses.cpp: In member function 'long long int segtree::get_val(long long int, long long int, long long int, long long int)':
horses.cpp:29:8: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
29 | if (ans>1e9) return 1e9+2;
| ^~~
horses.cpp: In member function 'void segtree::pull(int)':
horses.cpp:37:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
37 | remain[i].x=get_val(remain[2*i].x,remain[2*i].y,val_x[2*i],remain[2*i+1].x);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:41:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
41 | remain[i].y=get_val(remain[2*i].y,remain[2*i+1].x,remain[2*i+1].y,val_x[2*i+1]);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:96:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
96 | int best=seg.pos[1];
| ~~~~~~~~~^
horses.cpp:97:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
97 | int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:107:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
107 | int best=seg.pos[1];
| ~~~~~~~~~^
horses.cpp:108:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
108 | int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
| ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:118:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
118 | int best=seg.pos[1];
| ~~~~~~~~~^
horses.cpp:119:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
119 | int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15956 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15956 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
266 ms |
59268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15908 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
15896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15928 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
