Submission #28008

#	Time	Username	Problem	Language	Result	Execution time	Memory
28008		noobprogrammer	Horses (IOI15_horses)	C++14	100 / 100	263 ms	103604 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std; 
#define ii pair<int,int>
#define fi first
#define se second
typedef long long ll ;
typedef long double lf ;

const ll mod = 1e9 + 7 ;
int n ;
ii arr[500010] ;
pair< lf ,lf > st[2000010] ;
pair< ll ,ll > res[2000010] ;

void updval(int node){
	st[node].fi = st[2*node].fi + st[2*node+1].fi ; res[node].fi = res[2*node].fi * res[2*node+1].fi ;
	res[node].fi %= mod ;
	if( st[2*node].fi + st[2*node+1].se >= st[2*node].se ){
		st[node].se = st[2*node].fi + st[2*node+1].se ;
		res[node].se = ( res[2*node].fi * res[2*node+1].se ) %mod ;
	}
	else{
		st[node].se = st[2*node].se ;
		res[node].se = res[2*node].se ;
	}
}

void build(int node ,int f,int l){
	if(f == l){
		res[node] = {1LL * arr[f].fi , 1LL * arr[f].fi * arr[f].se } ;
		res[node].se %= mod ;
		st[node] = { log((lf)arr[f].fi) , log((lf)arr[f].fi * (lf)arr[f].se) } ;
		return ; 
	}
	build(2*node , f , (f+l)/2 ) ; build(2*node +1 , (f+l)/2 + 1 , l ) ;
	updval(node) ;
}

void upd(int node , int  f,int l , int x){

	if(f == l){
		res[node] = {1LL * arr[f].fi , 1LL * arr[f].fi * arr[f].se } ;
		res[node].se %= mod ;
		st[node] = { log((lf)arr[f].fi) , log((lf)arr[f].fi * (lf)arr[f].se) } ;
		return ; 
	}
	int mid = (f+l)>>1 ;
	if(mid < x) upd(2*node+1 , mid+1 , l , x) ;
	else upd(2*node , f , mid , x) ;
	updval(node) ;
	// printf("%d %d : %d %d %lf %lf" , f,  l,res[node].fi , ) ;
}

int init(int N, int X[], int Y[]) {
	n = N ;
	for(int i=0; i<n ;i++) arr[i] = {X[i] , Y[i]} ; 
	build(1 , 0 , n-1 ) ;
	return res[1].se ;
}

int updateX(int pos, int val) {	
	arr[pos].fi = val ;
	upd(1 , 0 , n-1, pos) ;
	return res[1].se ;
}

int updateY(int pos, int val) {
	arr[pos].se = val ;
	upd(1 , 0 , n-1, pos) ;
	return res[1].se ;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:6:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define se second
            ^
horses.cpp:59:16: note: in expansion of macro 'se'
  return res[1].se ;
                ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:6:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define se second
            ^
horses.cpp:65:16: note: in expansion of macro 'se'
  return res[1].se ;
                ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:6:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define se second
            ^
horses.cpp:71:16: note: in expansion of macro 'se'
  return res[1].se ;
                ^

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