| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 216911 | kshitij_sodani | Horses (IOI15_horses) | C++17 | 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 <iostream>
#include <bits/stdc++.h>
//#include <horses.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
int mod=1000000007;
int tree[2000001];
int tree2[2000001];
int tree3[2000001];
int aa[500001];
int bb[500001];
int n;
int build3(int no,int l,int r){
if(l==r){
tree3[no]=aa[l];
}
else{
int mid=(l+r)/2;
build3(no*2+1,l,mid);
build3(no*2+2,mid+1,r);
tree3[no]=(int)(((llo)tree3[no*2+1]*tree3[no*2+2])%mod);
}
}
int query3(int no,int l,int r,int ac,int bc){
if(l>=ac and r<=bc){
return tree3[no];
}
if(r<ac or bc<l){
return 1;
}
int mid=(l+r)/2;
return (int)(((llo)query3(no*2+1,l,mid,ac,bc)*query3(no*2+2,mid+1,r,ac,bc))%mod);
}
int update3(int no,int l,int r,int i,int val){
if(l==r and l==i){
tree3[no]=val;
}
else{
int mid=(l+r)/2;
if(i<=mid){
update3(no*2+1,l,mid,i,val);
}
else{
update3(no*2+2,mid+1,r,i,val);
}
tree3[no]=(int)(((llo)tree3[no*2+1]*tree3[no*2+2])%mod);
}
}
int build(int no,int l,int r){
if(l==r){
tree[no]=aa[l];
}
else{
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree[no]=(int)(min((llo)1000000001,(llo)tree[no*2+1]*tree[no*2+2]));
}
}
int update(int no,int l,int r,int i,int val){
if(l==r and l==i){
tree[no]=val;
}
else{
int mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,val);
}
else{
update(no*2+2,mid+1,r,i,val);
}
tree[no]=(int)(min((llo)1000000001,(llo)tree[no*2+1]*tree[no*2+2]));
}
}
int query(int no,int l,int r,int ac,int bc){
if(l>=ac and r<=bc){
return tree[no];
}
if(r<ac or bc<l){
return 1;
}
int mid=(l+r)/2;
return (int)(min((llo)1000000001,(llo)query(no*2+1,l,mid,ac,bc)*query(no*2+2,mid+1,r,ac,bc)));
}
int build2(int no,int l,int r){
if(l==r){
tree2[no]=l;
// cout<<no<<":"<<l<<endl;
}
else{
int mid=(l+r)/2;
build2(no*2+1,l,mid);
build2(no*2+2,mid+1,r);
// cout<<l<<","<<r<<end;
int xx=bb[tree2[no*2+1]]/bb[tree2[no*2+2]]+1;
if(bb[tree2[no*2+1]]%bb[tree2[no*2+2]]==0){
xx-=1;
}
// cout<<tree2[no*2+1]+1<<","<<tree2[no*2+2]<<","<<query(0,0,n-1,tree2[no*2+1]+1,tree2[no*2+2])<<":"<<query(0,0,n-1,tree2[no*2+1]+1,tree2[no*2+2])<<endl;
if(query(0,0,n-1,tree2[no*2+1]+1,tree2[no*2+2])>=xx){
tree2[no]=tree2[no*2+2];
}
else{
tree2[no]=tree2[no*2+1];
}
// cout<<l<<" "<<r<<" "<<no<<" "<<tree2[no]<<endl;
}
}
int update2(int no,int l,int r,int i){
if(l==r and l==i){
tree2[no]=l;
}
else{
int mid=(l+r)/2;
if(i<=mid){
update2(no*2+1,l,mid,i);
}
else{
update2(no*2+2,mid+1,r,i);
}
int xx=bb[tree2[no*2+1]]/bb[tree2[no*2+2]]+1;
if(bb[tree2[no*2+1]]%bb[tree2[no*2+2]]==0){
xx-=1;
}
if(query(0,0,n-1,tree2[no*2+1]+1,tree2[no*2+2])>=xx){
tree2[no]=tree2[no*2+2];
}
else{
tree2[no]=tree2[no*2+1];
}
}
}
int init(int nn,int x[],int y[]){
n=nn;
for(int i=0;i<n;i++){
aa[i]=x[i];
bb[i]=y[i];
}
build(0,0,n-1);
//cout<<1<<endl;
build2(0,0,n-1);
//cout<<1<<endl;
build3(0,0,n-1);
//cout<<1<<endl;
return (int)((query3(0,0,n-1,0,tree2[0])*bb[tree2[0]])%mod);
}
int updateX(int pos,int val){
update(0,0,n-1,pos-1,val);
update3(0,0,n-1,pos-1,val);
update2(0,0,n-1,pos-1);
return (int)((query3(0,0,n-1,0,tree2[0])*bb[tree2[0]])%mod);
}
int updateY(int pos,int val){
bb[pos-1]=val;
update2(0,0,n-1,pos-1);
return (int)((query3(0,0,n-1,0,tree2[0])*bb[tree2[0]])%mod);
}
int main(){
int ac[3];
int cc[3];
ac[0]=2;ac[1]=1;ac[2]=3;
cc[0]=1;cc[1]=2;cc[2]=2;
cout<<init(3,ac,cc)<<endl;
return 0;
}