Submission #298145

#	Time	Username	Problem	Language	Result	Execution time	Memory
298145		TMJN	Horses (IOI15_horses)	C++17	0 / 100	1086 ms	41080 KiB

horses

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


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

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,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;
	for(int i=0;i<(1<<20);i++){
		treemax[i]={0,1};
		treeupd[i]={0,1};
	}
	X=x;
	Y=y;
	for(int i=0;i<N;i++){
		updateX(i,X[i]);
		updateY(i,Y[i]);
	}
	return 0;
}

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

int updateY(int pos, int val) {
	update(1,0,(1<<19)-1,pos,N-1,val%modinv(Y[pos])%mod,log(val)-log(Y[pos]));
	Y[pos]=val;
	return treemax[1].second;
}

Compilation message (stderr)

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

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