Submission #550218

#	Time	Username	Problem	Language	Result	Execution time	Memory
550218		Hanksburger	Horses (IOI15_horses)	C++17	100 / 100	675 ms	41868 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const long long num=1000000001, mod=1000000007;
long long seg1[2000005], seg2[2000005], ind[2000005], x[500005], y[500005], n;
void buildSeg(long long i, long long l, long long r)
{
	if (l==r)
	{
		seg1[i]=seg2[i]=x[l];
		return;
	}
	long long mid=(l+r)/2;
	buildSeg(i*2, l, mid);
	buildSeg(i*2+1, mid+1, r);
	seg1[i]=seg1[i*2]*seg1[i*2+1]%mod;
	seg2[i]=min(num, seg2[i*2]*seg2[i*2+1]);
}
void updateSeg(long long i, long long l, long long r, long long pos, long long val)
{
	if (l==r)
	{
		seg1[i]=seg2[i]=val;
		return;
	}
	long long mid=(l+r)/2;
	if (pos<=mid)
		updateSeg(i*2, l, mid, pos, val);
	else
		updateSeg(i*2+1, mid+1, r, pos, val);
	seg1[i]=seg1[i*2]*seg1[i*2+1]%mod;
	seg2[i]=min(num, seg2[i*2]*seg2[i*2+1]);
}
long long querySeg(long long i, long long l, long long r, long long ql, long long qr, bool b)
{
	if (ql<=l && r<=qr)
	{
		if (b)
			return seg1[i];
		else
			return seg2[i];
	}
	long long mid=(l+r)/2, prod=1;
	if (l<=qr && ql<=mid)
		prod*=querySeg(i*2, l, mid, ql, qr, b);
	if (mid+1<=qr && ql<=r)
		prod*=querySeg(i*2+1, mid+1, r, ql, qr, b);
	if (b)
		return prod%mod;
	else
		return min(num, prod);
}
void buildInd(long long i, long long l, long long r)
{
	if (l==r)
	{
		ind[i]=l;
		return;
	}
	long long mid=(l+r)/2, indl, indr;
	buildInd(i*2, l, mid);
	buildInd(i*2+1, mid+1, r);
	indl=ind[i*2];
	indr=ind[i*2+1];
	if (y[indl]>querySeg(1, 0, n-1, indl+1, indr, 0)*y[indr])
		ind[i]=indl;
	else
		ind[i]=indr;
}
void updateInd(long long i, long long l, long long r, long long pos)
{
	if (l==r)
		return;
	long long mid=(l+r)/2, indl, indr;
	if (pos<=mid)
		updateInd(i*2, l, mid, pos);
	else
		updateInd(i*2+1, mid+1, r, pos);
	indl=ind[i*2];
	indr=ind[i*2+1];
	if (y[indl]>querySeg(1, 0, n-1, indl+1, indr, 0)*y[indr])
		ind[i]=indl;
	else
		ind[i]=indr;
}
long long solve()
{
	return querySeg(1, 0, n-1, 0, ind[1], 1)*y[ind[1]]%mod;
}
int init(int N, int X[], int Y[])
{
	n=N;
	for (long long i=0; i<n; i++)
		x[i]=X[i];
	for (long long i=0; i<n; i++)
		y[i]=Y[i];
	buildSeg(1, 0, n-1);
	buildInd(1, 0, n-1);
	return solve();
}
int updateX(int pos, int val)
{	
	updateSeg(1, 0, n-1, pos, val);
	updateInd(1, 0, n-1, pos);
	return solve();
}
int updateY(int pos, int val)
{
	y[pos]=val;
	updateInd(1, 0, n-1, pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:105:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  105 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:111:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |  return solve();
      |         ~~~~~^~

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