Submission #216903

#	Time	Username	Problem	Language	Result	Execution time	Memory
216903		kshitij_sodani	Horses (IOI15_horses)	C++17	0 / 100	445 ms	39416 KiB

horses

#include <iostream>
#include <bits/stdc++.h>
//#include <horses.h>
using namespace std;
typedef long long int llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
llo mod=1000000007;
llo tree[2000001];
llo tree2[2000001];
llo tree3[2000001];
llo aa[500001];
llo bb[500001];
llo n;
llo build3(llo no,llo l,llo r){
	if(l==r){
		tree3[no]=aa[l];
	}
	else{
		llo mid=(l+r)/2;
		build3(no*2+1,l,mid);
		build3(no*2+2,mid+1,r);
		tree3[no]=(tree[no*2+1]*tree[no*2+2])%mod;
	}
}
llo query3(llo no,llo l,llo r,llo aa,llo bb){
	if(l>=aa and r<=bb){
		return tree3[no];
	}
	if(r<aa or bb<l){
		return 1;
	}
	llo mid=(l+r)/2;
	return (query3(no*2+1,l,mid,aa,bb)*query3(no*2+2,mid+1,r,aa,bb))%mod;
}
llo update3(llo no,llo l,llo r,llo i,llo val){
	if(l==r and l==i){
		tree[no]=val;
	}
	else{
		llo 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);
		}
		tree[no]=(tree[no*2+1]*tree[no*2+2])%mod;
	}
}
llo build(llo no,llo l,llo r){
	if(l==r){
		tree[no]=aa[l];
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=min((llo)1000000001,tree[no*2+1]*tree[no*2+2]);
	}
}
llo update(llo no,llo l,llo r,llo i,llo val){
	if(l==r and l==i){
		tree[no]=val;
	}
	else{
		llo 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]=min((llo)1000000001,tree[no*2+1]*tree[no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	if(l>=aa and r<=bb){
		return tree[no];
	}
	if(r<aa or bb<l){
		return 1;
	}
	llo mid=(l+r)/2;
	return min((llo)1000000001,query(no*2+1,l,mid,aa,bb)*query(no*2+2,mid+1,r,aa,bb));
}
llo build2(llo no,llo l,llo r){
	if(l==r){
		tree2[no]=l;
	//	cout<<no<<":"<<l<<endl;
	}
	else{
		llo mid=(l+r)/2;
		build2(no*2+1,l,mid);
		build2(no*2+2,mid+1,r);
	//	cout<<l<<","<<r<<end;

		llo 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;
	}
}
llo update2(llo no,llo l,llo r,llo i){
	if(l==r and l==i){
		tree2[no]=l;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i);
		}
		else{
			update2(no*2+2,mid+1,r,i);
		}
		llo 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(llo 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 (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 (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 (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;
}*/

Compilation message (stderr)

horses.cpp: In function 'llo build3(llo, llo, llo)':
horses.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'llo query3(llo, llo, llo, llo, llo)':
horses.cpp:29:44: warning: declaration of 'bb' shadows a global declaration [-Wshadow]
 llo query3(llo no,llo l,llo r,llo aa,llo bb){
                                            ^
horses.cpp:16:5: note: shadowed declaration is here
 llo bb[500001];
     ^~
horses.cpp:29:44: warning: declaration of 'aa' shadows a global declaration [-Wshadow]
 llo query3(llo no,llo l,llo r,llo aa,llo bb){
                                            ^
horses.cpp:15:5: note: shadowed declaration is here
 llo aa[500001];
     ^~
horses.cpp: In function 'llo update3(llo, llo, llo, llo, llo)':
horses.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'llo build(llo, llo, llo)':
horses.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'llo update(llo, llo, llo, llo, llo)':
horses.cpp:79:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'llo query(llo, llo, llo, llo, llo)':
horses.cpp:80:43: warning: declaration of 'bb' shadows a global declaration [-Wshadow]
 llo query(llo no,llo l,llo r,llo aa,llo bb){
                                           ^
horses.cpp:16:5: note: shadowed declaration is here
 llo bb[500001];
     ^~
horses.cpp:80:43: warning: declaration of 'aa' shadows a global declaration [-Wshadow]
 llo query(llo no,llo l,llo r,llo aa,llo bb){
                                           ^
horses.cpp:15:5: note: shadowed declaration is here
 llo aa[500001];
     ^~
horses.cpp: In function 'llo build2(llo, llo, llo)':
horses.cpp:115:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'llo update2(llo, llo, llo, llo)':
horses.cpp:139:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:152:50: warning: conversion to 'int' from 'llo {aka long long int}' may alter its value [-Wconversion]
  return (query3(0,0,n-1,0,tree2[0])*bb[tree2[0]])%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:158:50: warning: conversion to 'int' from 'llo {aka long long int}' may alter its value [-Wconversion]
  return (query3(0,0,n-1,0,tree2[0])*bb[tree2[0]])%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:163:50: warning: conversion to 'int' from 'llo {aka long long int}' may alter its value [-Wconversion]
  return (query3(0,0,n-1,0,tree2[0])*bb[tree2[0]])%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23