Submission #1056211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056211		Muhammad_Aneeq	Horses (IOI15_horses)	C++17	100 / 100	129 ms	59956 KiB

horses

#include "horses.h"
#include <cmath>
#include <vector>
using namespace std;
int const MAXN=5e5+10,mod=1e9+7;
vector<int>x,y;
struct node
{
	long long val,maxval;
	long double cnt,maxcnt=0;
};
node seg[4*MAXN]={};
void build(int i,int st,int en)
{
	if (st==en)
	{
		seg[i].val=seg[i].maxval=x[st];
		seg[i].maxval*=y[st];
		seg[i].maxval%=mod;
		seg[i].cnt=log2(x[st]);
		seg[i].maxcnt=seg[i].cnt+log2(y[st]);
		return ;
	}
	int mid=(st+en)/2;
	build(i*2,st,mid);build(i*2+1,mid+1,en);
	int lc=i*2,rc=i*2+1;
	seg[i].val=(seg[lc].val*seg[rc].val)%mod;
	seg[i].cnt=seg[lc].cnt+seg[rc].cnt;
	if (seg[lc].maxcnt<seg[lc].cnt+seg[rc].maxcnt)
	{
		seg[i].maxcnt=seg[lc].cnt+seg[rc].maxcnt;
		seg[i].maxval=(seg[lc].val*seg[rc].maxval)%mod;
	}
	else
	{
		seg[i].maxcnt=seg[lc].maxcnt;
		seg[i].maxval=seg[lc].maxval;
	}
}
void update(int i,int r,int st,int en)
{
	if (st==en)
	{
		seg[i].val=seg[i].maxval=x[r];
		seg[i].maxval*=y[r];
		seg[i].maxval%=mod;
		seg[i].cnt=log2(x[r]);
		seg[i].maxcnt=seg[i].cnt+log2(y[r]);
		return ;
	}
	int mid=(st+en)/2;
	if (r<=mid)
		update(i*2,r,st,mid);
	else
		update(i*2+1,r,mid+1,en);
	int lc=i*2,rc=i*2+1;
	seg[i].val=(seg[lc].val*seg[rc].val)%mod;
	seg[i].cnt=seg[lc].cnt+seg[rc].cnt;
	if (seg[lc].maxcnt<seg[lc].cnt+seg[rc].maxcnt)
	{
		seg[i].maxcnt=seg[lc].cnt+seg[rc].maxcnt;
		seg[i].maxval=(seg[lc].val*seg[rc].maxval)%mod;
	}
	else
	{
		seg[i].maxcnt=seg[lc].maxcnt;
		seg[i].maxval=seg[lc].maxval;
	}
}
int init(int N, int X[], int Y[])
{
	for (int i=0;i<N;i++)
	{
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	build(1,0,N-1);
	return seg[1].maxval;
}
int updateX(int pos, int val)
{
	x[pos]=val;
	update(1,pos,0,x.size()-1);
	return seg[1].maxval;
}
int updateY(int pos, int val)
{
	y[pos]=val;
	update(1,pos,0,x.size()-1);
	return seg[1].maxval;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:78:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |  return seg[1].maxval;
      |         ~~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:83:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   83 |  update(1,pos,0,x.size()-1);
      |                 ~~~~~~~~^~
horses.cpp:84:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return seg[1].maxval;
      |         ~~~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   89 |  update(1,pos,0,x.size()-1);
      |                 ~~~~~~~~^~
horses.cpp:90:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return seg[1].maxval;
      |         ~~~~~~~^~~~~~

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