oj.uz

Submission #1085536

# Submission time Handle Problem Language Result Execution time Memory
1085536 2024-09-08T11:45:01 Z 4QT0R Horses (IOI15_horses) C++17
0 / 100
 18 ms 10576 KB 
#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;
}

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

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 10576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 0 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -