Submission #396806

#	Time	Username	Problem	Language	Result	Execution time	Memory
396806		rainboy	Horses (IOI15_horses)	C11	100 / 100	152 ms	30916 KiB

horses

#include "horses.h"
#include <string.h>

#define N	500000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define MD	1000000007
#define INF	0x3f3f3f3f

long long min(long long a, long long b) { return a < b ? a : b; }

int xx[N], yy[N], pp[N_ * 2], qq[N_ * 2], suf_[N_ * 2], prod[N_ * 2], prod_[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	prod[i] = min((long long) prod[l] * prod[r], INF);
	prod_[i] = (long long) prod_[l] * prod_[r] % MD;
	if (pp[r] == 0 || ((long long) pp[l] * qq[r]) / ((long long) qq[l] * pp[r]) >= prod[r])
		pp[i] = pp[l], qq[i] = qq[l] * prod[r], suf_[i] = suf_[l];
	else
		pp[i] = pp[r], qq[i] = qq[r], suf_[i] = (long long) prod_[l] * suf_[r] % MD;
}

int init(int n, int *xx_, int *yy_) {
	int i;

	memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++) {
		prod[n_ + i] = prod_[n_ + i] = i < n ? xx[i] : 1;
		pp[n_ + i] = i < n ? yy[i] : 0, qq[n_ + i] = 1, suf_[n_ + i] = (long long) xx[i] * (i < n ? yy[i] : 0) % MD;
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
	return suf_[1];
}

int updateX(int i, int x) {
	xx[i] = x;
	prod[n_ + i] = prod_[n_ + i] = xx[i], suf_[n_ + i] = (long long) xx[i] * yy[i] % MD;
	i += n_;
	while (i > 1)
		pul(i >>= 1);
	return suf_[1];
}

int updateY(int i, int y) {
	yy[i] = y;
	pp[n_ + i] = yy[i], qq[n_ + i] = 1, suf_[n_ + i] = (long long) xx[i] * yy[i] % MD;
	i += n_;
	while (i > 1)
		pul(i >>= 1);
	return suf_[1];
}

Compilation message (stderr)

horses.c: In function 'pul':
horses.c:16:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  prod[i] = min((long long) prod[l] * prod[r], INF);
      |            ^~~
horses.c:17:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |  prod_[i] = (long long) prod_[l] * prod_[r] % MD;
      |             ^
horses.c:21:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |   pp[i] = pp[r], qq[i] = qq[r], suf_[i] = (long long) prod_[l] * suf_[r] % MD;
      |                                           ^
horses.c: In function 'init':
horses.c:27:20: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   27 |  memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
      |                    ^
horses.c:27:54: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   27 |  memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
      |                                                      ^
horses.c:33:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |   pp[n_ + i] = i < n ? yy[i] : 0, qq[n_ + i] = 1, suf_[n_ + i] = (long long) xx[i] * (i < n ? yy[i] : 0) % MD;
      |                                                                  ^
horses.c: In function 'updateX':
horses.c:42:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  prod[n_ + i] = prod_[n_ + i] = xx[i], suf_[n_ + i] = (long long) xx[i] * yy[i] % MD;
      |                                                       ^
horses.c: In function 'updateY':
horses.c:51:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |  pp[n_ + i] = yy[i], qq[n_ + i] = 1, suf_[n_ + i] = (long long) xx[i] * yy[i] % MD;
      |                                                     ^

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