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>
using namespace std;
long long md=1e9+7;
long long inf=1e9+1;
long long y[500005];
long long x[500005];
int n;
struct node{
long long y,rall,pre,suf,ans,all;
node(long long _y=0,long long _rall=0,long long _pre=0,long long _suf=0,long long _ans=0,long long _all=0){
y=_y,rall=_rall,pre=_pre,suf=_suf,ans=_ans,all=_all;
}
friend node operator+(node a,node b){
node c;
c.rall=(a.rall*b.rall)%md;
c.all=min(a.all*b.all,inf);
if(min(a.suf*b.pre,inf)>a.y){
c.y=b.y;
c.pre=min(a.all*b.pre,inf);
c.suf=b.suf;
c.ans=(a.rall*b.ans)%md;
}else{
c.y=a.y;
c.pre=a.pre;
c.suf=min(a.suf*b.all,inf);
c.ans=a.ans;
}
return c;
}
};
struct segtree{
node info[2000005];
void upd(int st,int en,int i,int pos,node val){
if(st>pos||en<pos)return;
if(st==en)return void(info[i]=val);
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
info[i]=info[i*2]+info[i*2+1];
}
void build(int st,int en,int i){
//cerr<<st<<' '<<en<<"\n";
if(st==en)return void(info[i]=node(y[st],x[st],min(x[st]*y[st],inf),x[st],(x[st]*y[st])%md,x[st]));
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
}
}tr;
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];
tr.build(1,N,1);
return tr.info[1].ans;
}
int updateX(int pos, int val) {
pos++;
x[pos]=val;
tr.upd(1,n,1,pos,node(y[pos],x[pos],min(x[pos]*y[pos],inf),x[pos],(x[pos]*y[pos])%md,x[pos]));
return tr.info[1].ans;
}
int updateY(int pos, int val) {
pos++;
y[pos]=val;
tr.upd(1,n,1,pos,node(y[pos],x[pos],min(x[pos]*y[pos],inf),x[pos],(x[pos]*y[pos])%md,x[pos]));
return tr.info[1].ans;
}
Compilation message (stderr)
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:55:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
55 | return tr.info[1].ans;
| ~~~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:62:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
62 | return tr.info[1].ans;
| ~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:69:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
69 | return tr.info[1].ans;
| ~~~~~~~~~~~^~~
# | 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... |