Submission #1085553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085553		4QT0R	Horses (IOI15_horses)	C++17	100 / 100	245 ms	78160 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define ld long double

struct node{
	ld sum;
	ld max_pref;
	ll ind;
};

const ll mod=1e9+7;

const ll base=1<<19;
node max_tree[2*base];
ll xprod[2*base];
ll cost[base+1];

ll fast_pow(ll a, ll b){
	if (b==1)return a;
	ll cur=fast_pow(a,b/2);
	cur=(cur*cur)%mod;
	if (b&1)cur=(cur*a)%mod;
	return cur;
}

void start(int v){
	if (v>=base){
		if (!xprod[v])xprod[v]=1;
		if (!cost[v-base])cost[v-base]=1;
		return;
	}
	start(2*v);
	start(2*v+1);
	xprod[v]=(xprod[2*v]*xprod[2*v+1])%mod;
	max_tree[v]=max_tree[2*v];
	if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
		max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
		max_tree[v].ind=max_tree[2*v+1].ind;
	}
	max_tree[v].sum+=max_tree[2*v+1].sum;
}

void mult(ll &a, ll b){
	a=(a*b)%mod;
}

ll ans(int v){
	ll odp=cost[v];
	v+=base+1;
	while(v>1){
		if (v&1)mult(odp,xprod[v-1]);
		v>>=1;
	}
	return odp;
}

int init(int n, int x[], int y[]){
	for (int i = 1; i<=n; i++){
		cost[i]=y[i-1];
		xprod[i+base]=x[i-1];
		max_tree[i+base].sum=logl(x[i-1])+logl(y[i-1])-logl(i==1?1:y[i-2]);
		max_tree[i+base].max_pref=max_tree[i+base].sum;
		max_tree[i+base].ind=i;
	}
	start(1);
	return ans(max_tree[1].ind);
}

int updateX(int pos, int val){
	pos++;
	int v=pos+base;
	xprod[v]=val;
	max_tree[v].sum=logl(val)+logl(cost[pos])-logl(cost[pos-1]);
	max_tree[v].max_pref=max_tree[v].sum;
	v>>=1;
	while(v){
		xprod[v]=xprod[2*v];
		mult(xprod[v],xprod[2*v+1]);

		max_tree[v]=max_tree[2*v];
		if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
			max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
			max_tree[v].ind=max_tree[2*v+1].ind;
		}
		max_tree[v].sum+=max_tree[2*v+1].sum;
		v>>=1;
	}
	return ans(max_tree[1].ind);
}

int updateY(int pos, int val){
	pos++;
	int v=pos+base;
	int v2=pos+1+base;
	cost[pos]=val;
	max_tree[v].sum=logl(xprod[v])+logl(cost[pos])-logl(cost[pos-1]);
	max_tree[v].max_pref=max_tree[v].sum;
	v>>=1;
	max_tree[v2].sum=logl(xprod[v2])+logl(cost[pos+1])-logl(cost[pos]);
	max_tree[v2].max_pref=max_tree[v2].sum;
	v2>>=1;
	while(v){
		max_tree[v]=max_tree[2*v];
		if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
			max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
			max_tree[v].ind=max_tree[2*v+1].ind;
		}
		max_tree[v].sum+=max_tree[2*v+1].sum;
		v>>=1;
		max_tree[v2]=max_tree[2*v2];
		if (max_tree[v2].sum+max_tree[2*v2+1].max_pref>max_tree[v2].max_pref){
			max_tree[v2].max_pref=max_tree[v2].sum+max_tree[2*v2+1].max_pref;
			max_tree[v2].ind=max_tree[2*v2+1].ind;
		}
		max_tree[v2].sum+=max_tree[2*v2+1].sum;
		v2>>=1;
	}
	return ans(max_tree[1].ind);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:68:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:68:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:90:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:90:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:120:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return ans(max_tree[1].ind);
      |             ~~~~~~~~~~~~^~~
horses.cpp:120:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return ans(max_tree[1].ind);
      |         ~~~^~~~~~~~~~~~~~~~~

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