Submission #121339

#	Time	Username	Problem	Language	Result	Execution time	Memory
121339		CaroLinda	Horses (IOI15_horses)	C++14	0 / 100	1550 ms	524288 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

#define ll long long
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MOD = 1e9+7 ;
const int maxn=5e5+10;

using namespace std ;

int n ;

struct segOfSum
	{
		
		double v[maxn*4] ;
		
		void pointUpd(int pos, int l, int r,int x , double val)
		{
			if(l==r) { v[pos] = val ; return ; }
			int mid = (l+r)/2 ;
			if(x<=mid) pointUpd(pos*2,l,mid,x,val) ;
			else pointUpd(pos*2+1,mid+1,r,x,val) ;
			v[pos] = v[pos*2] + v[pos*2+1] ;
		}
		
		double query(int pos, int l, int r, int beg, int en)
		{
			if(l>en || r < beg) return 0 ;
			if(l>=beg && r<=en) return v[pos] ;
			int mid=(l+r)/2 ;
			double rl = query(pos*2,l,mid,beg,en) ;
			double rr = query(pos*2+1,mid+1,r,beg,en) ;
			return rl+rr ;
		}
			
} ;

//------- x -------

int bit[maxn] ;

void add(int x, int val)
{ for(int i=x;i<maxn;i+=(i&-i)) bit[i]+=val ; }

int queryb(int x)
{
	int tot = 0 ;
	for(int i = x ; i>0 ; i--) tot += bit[i] ;
	return tot ;
}

//------- x -------
	
double tree[maxn*4] ;
int best[maxn*4] ;
segOfSum mySeg ;

int m(int l, int r){return (l+r)/2 ;}

void merge(int pos)
{
	int index1 = best[pos*2] ;
	int index2 = best[pos*2+1] ;
	
	int q = queryb(index2) - queryb(index1) ;
	
	tree[pos] = tree[pos*2+1] ;
	best[pos] = best[pos*2+1] ;
	
	double x = mySeg.query(1,0,n,index1+1,index2) ;
	
	if( q<30 && (x + tree[pos*2+1] < tree[pos*2]) ) 
		tree[pos] = tree[pos*2] , best[pos] = best[pos*2];
	
}

void pointUpd(int pos, int l, int r, int x, double v)
{
	if(l==r)
	{
		tree[pos] = v ;
		best[pos] = x ;
		return ;
	}
	if(x<=m(l,r)) pointUpd(pos*2,l,m(l,r),x,v) ;
	else pointUpd(pos*2+1, m(l,r)+1,r,x,v) ;
	merge(pos) ;
}
	
void print(int pos, int l, int r)
{
	printf("%d %d -> %d , %f\n" , l , r , best[pos] , pow(2,tree[pos])) ;
	if(l==r) return ;
	print(pos*2,l,m(l,r)) ;
	print(pos*2+1, m(l,r)+1,r ) ;
}	
	
//------- x -------

int  x[maxn] , y[maxn] ;

ll expo(ll x, int n)
{
	if(n==0) return 1 ;
	if(n==1) return x ;
	if(n%2==0)
	{
		ll aux = expo(x, n/2) ;
		return (aux*aux)%MOD ;
	}
	
	ll aux = expo(x,n-1) ;
	
	return (aux*x)%MOD ;
	
}

ll ans()
{
	
	double k = mySeg.query(1,0,n,0, best[1] ) ;
	
	k += log2(y[ best[1] ] ) ;
	int myInt = int(k) ;
	
	while(myInt < k) myInt ++ ;
	
	double now = expo(2,--myInt) * pow(2,k-myInt);
	
	ll myAns = int(now) ;
	
	while(myAns<now) myAns ++ ;
	
	return myAns%MOD ;
	
		
} ;

int updateY(int pos, int val)
{
	pos++ ;
	pointUpd(1,0,n,pos,log2(val)) ;
	y[pos] = val ;
	return ans() ;
}

int updateX(int pos, int val)
{
	pos++ ;
	mySeg.pointUpd(1,0,n,pos,log2(val)) ;
	if(x[pos] > 1) add(pos,-1) ;
	if(val > 1) add(pos,1) ;
	pointUpd(1,0,n,pos,log2(y[pos])) ;
	x[pos] = val ;
	return ans() ;
}

int init(int N, int X[] , int Y[])
{
	//Crapy initializations
	n = N ;
	for(int i = n ; i > 0 ; i--) x[i] = X[i-1] , y[i] = Y[i-1] ;
	
	lp(i,1,n+1)
		mySeg.pointUpd(1,0,n,i,log2(x[i])) ;
	lp(i,1,n+1)
		if(x[i]>1) add(i,1) ;
	lp(i,1,n+1)
		pointUpd(1,0,n,i,log2(y[i])) ;
		
	return ans() ;
	
}

Compilation message (stderr)

horses.cpp: In function 'long long int expo(long long int, int)':
horses.cpp:109:20: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll expo(ll x, int n)
                    ^
horses.cpp:17:5: note: shadowed declaration is here
 int n ;
     ^
horses.cpp:109:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 ll expo(ll x, int n)
                    ^
horses.cpp:107:6: note: shadowed declaration is here
 int  x[maxn] , y[maxn] ;
      ^
horses.cpp: In function 'long long int ans()':
horses.cpp:135:19: warning: conversion to '__gnu_cxx::__promote_2<int, double, double, double>::__type {aka double}' from 'long long int' may alter its value [-Wconversion]
  double now = expo(2,--myInt) * pow(2,k-myInt);
               ~~~~^~~~~~~~~~~
horses.cpp:135:22: warning: operation on 'myInt' may be undefined [-Wsequence-point]
  double now = expo(2,--myInt) * pow(2,k-myInt);
                      ^~~~~~~
horses.cpp:139:14: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
  while(myAns<now) myAns ++ ;
              ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:151:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans() ;
         ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:162:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans() ;
         ~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:178:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans() ;
         ~~~^~

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