| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 310695 | keta_tsimakuridze | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
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 int long long
using namespace std;
const int N=5e5+5,mod=1e9+7,Mx=1e9;
int x[N],y[N],k,t,ind,c,m,n;
struct node {
int l;
int r;
int Y;
int b;
int bl;
int br;
} tree[4*N];
void update(int u,int ind,int l,int r,int valx,int valy) {
if(l>ind || r<ind) return;
if(l==r) {
tree[u].l=valx;
// tree[u].X=valx;
tree[u].Y=valy;
tree[u].r=1;
if(valx*valy>Mx) {
tree[u].b=1;
} else tree[u].b=0;
return;
}
int mid=(l+r)/2;
update(2*u,ind,l,mid,valx,valy);
update(2*u+1,ind,mid+1,r,valx,valy);
if(tree[2*u].br||tree[2*u+1].bl || tree[2*u].r*tree[2*u+1].l>Mx || tree[2*u].r*tree[2*u+1].l*tree[2*u+1].Y>tree[2*u].Y ) {
// tree[2*u].l*tree[2*u].r*tree[2*u+1].l
if(tree[2*u].b||tree[2*u+1].bl || tree[2*u].l*tree[2*u].r*tree[2*u+1].l>Mx) {
tree[u].bl=1;
} else tree[u].bl=0;
tree[u].r=tree[2*u+1].r;
tree[u].br=tree[2*u+1].br;
tree[u].l=tree[2*u].l*tree[2*u].r%mod*tree[2*u+1].l%mod;
if(tree[u].bl || tree[u].br || tree[u].l*tree[u].r>Mx) {
tree[u].b=1;
} else tree[u].b=0;
tree[u].Y=tree[2*u+1].Y;
} else {
tree[u].l=tree[2*u].l;
tree[u].bl=tree[2*u].bl;
tree[u].Y=tree[2*u].Y;
tree[u].r=tree[2*u+1].r*tree[2*u+1].l%mod*tree[2*u].r%mod;
if(tree[2*u+1].b || tree[2*u].br ||tree[2*u+1].r*tree[2*u+1].l*tree[2*u].r>Mx) {
tree[u].br=1;
} else tree[u].br=0;
if(tree[u].br || tree[u].bl || tree[u].l*tree[u].r>Mx) {
tree[u].b=1;
} else tree[u].b=0;
}
}
void go(int u,int l,int r) {
cout<<l<<" "<<r<<" "<<tree[u].l<<" "<<tree[u].r<<" "<<tree[u].Y<<endl;
if(l==r) {
return;
}
int mid=(l+r)/2;
go(2*u,l,mid);
go(2*u+1,mid+1,r);
}
int init(int nn,int X[],int Y[]) {
n=nn;
for(k=1; k<=n; k++) {
x[k]=X[k-1];
y[k]=Y[k-1];
update(1,k,1,n,x[k],y[k]);
}
//go(1,1,n);
return tree[1].l*tree[1].Y%mod;
}
int updateX(int ind,int c) {
ind++;
update(1,ind,1,n,c,y[ind]);
x[ind]=c;
return tree[1].l*tree[1].Y%mod;
}
int updateY(int ind,int c){
ind++;
update(1,ind,1,n,x[ind],c);
y[ind]=c;
return tree[1].l*tree[1].Y%mod;
}