Submission #367959

#	Time	Username	Problem	Language	Result	Execution time	Memory
367959		dennisstar	Horses (IOI15_horses)	C++17	100 / 100	347 ms	67180 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

struct {
	ll v, x, y;
	double dv, dx, dy;
}st[1<<20];

void upd(int i, int s, int e, int t, int x, int y) {
	auto &n=st[i];
	if (s==e) {
		if (x) n.x=x, n.dx=log(x);
		if (y) n.y=y, n.dy=log(y);
		n.v=n.x*n.y%MOD;
		n.dv=n.dx+n.dy;
		return ;
	}

	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, x, y);
	else upd(i*2+1, m+1, e, t, x, y);

	auto &l=st[i*2], &r=st[i*2+1];
	n.x=l.x*r.x%MOD;
	n.dx=l.dx+r.dx;
	tie(n.dv, n.v)=
		max(pair<double, ll>(l.dv, l.v),
		pair<double, ll>(l.dx+r.dv, l.x*r.v%MOD));
}

int n;

int init(int n, int *x, int *y) {
	::n=n;
	for (int i=0; i<n; i++)
		upd(1, 0, n-1, i, x[i], y[i]);
	return st[1].v;
}

int updateX(int p, int v) {
	upd(1, 0, n-1, p, v, 0);
	return st[1].v;
}

int updateY(int p, int v) {
	upd(1, 0, n-1, p, 0, v);
	return st[1].v;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:38:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   38 | int init(int n, int *x, int *y) {
      |                               ^
horses.cpp:36:5: note: shadowed declaration is here
   36 | int n;
      |     ^
horses.cpp:42:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   42 |  return st[1].v;
      |         ~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:47:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   47 |  return st[1].v;
      |         ~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:52:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |  return st[1].v;
      |         ~~~~~~^

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