Submission #1085534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085534	2024-09-08T11:43:23 Z	4QT0R	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KB

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<<3;
node max_tree[2*base];
ll xprod[2*base];
ll cost[500002];

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(ll v){
	if (v>=base){
		if (!xprod[v])xprod[v]=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(ll v){
	ll odp=cost[v];
	v+=base+1;
	while(v>1){
		if (v&1)mult(odp,xprod[v-1]);
		v>>=1;
	}
	return odp;
}

ll init(ll n, ll x[], ll y[]){
	for (ll 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);
}

ll updateX(ll pos, ll val){
	pos++;
	ll 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);
}

ll updateY(ll pos, ll val){
	pos++;
	ll v=pos+base;
	ll 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

/usr/bin/ld: /tmp/cc234okO.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x113): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x16d): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status