Submission #298186

#	Time	Username	Problem	Language	Result	Execution time	Memory
298186		TMJN	Horses (IOI15_horses)	C++17	0 / 100	264 ms	70264 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
constexpr long long mod=1000000007;


pair<long double,long long> treemax[1<<20],treeupd[1<<20];
int N,*X,*Y;
long double dx[500000],dy[500000];

long long pw(long long x,int y){
	long long a=1;
	while(y){
		if(y&1)a=a*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return a;
}

long long modinv(long long x){
	return pw(x,mod-2);
}

void update(int k,int l,int r,int p,int q,long long val,long double ln){
	if(q<l||r<p)return;
	else if(p<=l&&r<=q){
		treemax[k].second*=val;
		treemax[k].second%=mod;
		treemax[k].first+=ln;
		treeupd[k].second*=val;
		treeupd[k].second%=mod;
		treeupd[k].first+=ln;
	}
	else{
		treemax[k+k].second*=treeupd[k].second;
		treemax[k+k+1].second*=treeupd[k].second;
		treemax[k+k].second%=mod;
		treemax[k+k+1].second%=mod;
		treeupd[k+k].second*=treeupd[k].second;
		treeupd[k+k+1].second*=treeupd[k].second;
		treeupd[k+k].second%=mod;
		treeupd[k+k+1].second%=mod;
		treemax[k+k].first+=treeupd[k].first;
		treemax[k+k+1].first+=treeupd[k].first;
		treeupd[k+k].first+=treeupd[k].first;
		treeupd[k+k+1].first+=treeupd[k].first;
		treeupd[k].second=1;
		treeupd[k].first=0;
		update(k+k,l,(l+r)/2,p,q,val,ln);
		update(k+k+1,(l+r)/2+1,r,p,q,val,ln);
		treemax[k]=max(treemax[k+k],treemax[k+k+1]);
	}
}


int init(int n, int x[], int y[]) {
	N=n;
	X=x;
	Y=y;
	long double ld=0;
	long long ll=1;
	for(int i=0;i<N;i++){
		dx[i]=logl(X[i]);
		dy[i]=logl(Y[i]);
		ll*=Y[i];
		ll%=mod;
		ld+=dy[i];
		treemax[i+(1<<19)]={ld+dx[i],ll*X[i]%mod};
	}
	for(int i=(1<<19)-1;i;i--){
		treemax[i]=max(treemax[i+i],treemax[i+i+1]);
		treeupd[i]={0,1};
	}
	return treemax[1].second;
}

int updateX(int pos, int val) {	
	long double ld=logl(val);
	update(1,0,(1<<19)-1,pos,N-1,val*modinv(X[pos])%mod,ld-dx[pos]);
	X[pos]=val;
	dx[pos]=ld;
	return treemax[1].second;
}

int updateY(int pos, int val) {
	long double ld=logl(val);
	update(1,0,(1<<19)-1,pos,pos,val*modinv(Y[pos])%mod,ld-dx[pos]);
	Y[pos]=val;
	dy[pos]=ld;
	return treemax[1].second;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:75:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  return treemax[1].second;
      |         ~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:83:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  return treemax[1].second;
      |         ~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  return treemax[1].second;
      |         ~~~~~~~~~~~^~~~~~

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