Submission #512530

#	Time	Username	Problem	Language	Result	Execution time	Memory
512530		AdamGS	Horses (IOI15_horses)	C++17	17 / 100	51 ms	21204 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
const ll MOD=1e9+7;
ll X[LIM], Y[LIM], tr[4*LIM], N=1, n;
ll cnt(int l, int r) {
	if(r<l) return 1;
	l+=N; r+=N;
	ll ans=tr[l];
	if(l!=r) ans=(ans*tr[r])%MOD;
	while(l/2!=r/2) {
		if(l%2==0) ans=(ans*tr[l+1])%MOD;
		if(r%2==1) ans=(ans*tr[r-1])%MOD;
		l/=2; r/=2;
	}
	return ans;
}
ll solve() {
	ll p=1, k=n;
	while(p<MOD && k>0) {
		--k;
		p*=X[k];
	}
	if(p>=MOD) ++k;
	p=1;
	ll ans=0, x=cnt(0, k-1);
	while(k<n) {
		p*=X[k];
		ans=max(ans, p*Y[k]);
		++k;
	}
	ans%=MOD;
	ans=(ans*x)%MOD;
	return ans;
}
int init(int D, int A[], int B[]) {
	n=D;
	while(N<n) N*=2;
	rep(i, 2*N) tr[i]=1;
	rep(i, n) {
		X[i]=A[i];
		Y[i]=B[i];
		tr[N+i]=X[i];
	}
	for(int i=N-1; i>=0; --i) tr[i]=(tr[2*i]*tr[2*i+1])%MOD;
	return solve();
}
 
int updateX(int pos, int val) {	
	X[pos]=val;
	pos+=N;
	tr[pos]=val;
  	pos/=2;
	while(pos) {
		tr[pos]=(tr[2*pos]*tr[2*pos+1])%MOD;
		pos/=2;
	}
	return solve();
}
 
int updateY(int pos, int val) {
	Y[pos]=val;
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'll cnt(int, int)':
horses.cpp:16:3: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   16 |  l+=N; r+=N;
      |  ~^~~
horses.cpp:16:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   16 |  l+=N; r+=N;
      |        ~^~~
horses.cpp: In function 'll solve()':
horses.cpp:34:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   34 |  ll ans=0, x=cnt(0, k-1);
      |                     ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:53:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   53 |  for(int i=N-1; i>=0; --i) tr[i]=(tr[2*i]*tr[2*i+1])%MOD;
      |            ~^~
horses.cpp:54:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:59:5: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 |  pos+=N;
      |  ~~~^~~
horses.cpp:66:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   66 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:71:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   71 |  return solve();
      |         ~~~~~^~

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