| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 624592 | NicolaAbusaad2014 | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
struct segment_tree
{
struct node
{
long double value;
long pos,left,right;
};
node dum;
vector<node>tree;
vector<long double>upd;
node operation(node x,node z)
{
node ret;
if(x.value>=z.value){
ret.value=x.value;
ret.pos=x.pos;
}
else{
ret.value=z.value;
ret.pos=z.pos;
}
ret.left=min(x.left,z.left);
ret.right=max(x.right,z.right);
return ret;
}
void push(long node)
{
tree[node].value+=upd[node];
if(node<tree.size()){
upd[node*2]+=upd[node];
upd[(node*2)+1]+=upd[node];
}
upd[node]=0;
}
void build(vector<long double>v)
{
tree.clear();
upd.clear();
int x=((v.size())*2)-1;
while(x&(x-1)){
x=x&(x-1);
}
tree.resize(x*2);
upd.resize(x*2);
dum.value=-1e9;
dum.left=-1e9;
dum.right=1e9;
for(long i=0;i<v.size();i++){
tree[i+x].value=v[i];
tree[i+x].pos=i;
tree[i+x].left=i;
tree[i+x].right=i;
}
for(long i=v.size();i<x;i++){
tree[i+x].value=-1e9;
tree[i+x].pos=i;
tree[i+x].left=i;
tree[i+x].right=i;
}
for(long i=x-1;i>0;i--){
tree[i]=operation(tree[i*2],tree[(i*2)+1]);
}
}
node get(int l,int r,int node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return dum;
}
if(tree[node].left>=l&&tree[node].right<=r){
return tree[node];
}
return operation(get(l,r,node*2),get(l,r,(node*2)+1));
}
void update(int l,int r,long double z,int node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return;
}
if(tree[node].left>=l&&tree[node].right<=r){
upd[node]+=z;
push(node);
return;
}
update(l,r,z,node*2);
update(l,r,z,(node*2)+1);
tree[node]=operation(tree[node*2],tree[(node*2)+1]);
}
};
segment_tree st;
long n;
vector<long long>x,y,tot;
vector<long double>v;
int init(int N, int X[], int Y[]) {
n=N;
x.resize(n);
y.resize(n);
tot.resize(n);
v.resize(n);
REP(i,0,n){
x[i]=X[i];
y[i]=Y[i];
}
v[0]=log(x[0])+log(y[0]);
tot[0]=(x[0]*y[0])%mod;
REP(i,1,n){
v[i]=v[i-1]+log(x[i])+log(y[i])-log(y[i-1]);
tot[i]=(((tot[i-1]*x[i])%mod)*((y[i]*inv(y[i-1]))%mod))%mod;
}
st.build(v);
N=st.get(0,n-1).pos;
return tot[N];
}
int updateX(int pos, long long val) {
st.update(pos,n-1,log(val)-log(x[pos]));
tot[pos]*=val;
tot[pos]%=mod;
tot[pos]*=inv(x[pos]);
tot[pos]%=mod;
x[pos]=val;
pos=st.get(0,n-1).pos;
return tot[pos];
}
int updateY(int pos, long long val) {
st.update(pos,pos,log(val)-log(y[pos]));
tot[pos]*=val;
tot[pos]%=mod;
tot[pos]*=inv(y[pos]);
tot[pos]%=mod;
y[pos]=val;
pos=st.get(0,n-1).pos;
return tot[pos];
}