Submission #513850

#	Time	Username	Problem	Language	Result	Execution time	Memory
513850		sliviu	Horses (IOI15_horses)	C++14	100 / 100	149 ms	50372 KiB

horses

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

using namespace std;

const int mod = 1e9 + 7;
int n, x[1 << 19], y[1 << 19];

struct node {
	int ans, x, y;
	double rans, rx, ry;
} st[1 << 20];

node Merge(node l, node r) {
	node ans;
	ans.x = 1LL * l.x * r.x % mod;
	ans.rx = l.rx + r.rx;
	if (l.rans > l.rx + r.rans)
		ans.ans = l.ans, ans.rans = l.rans;
	else
		ans.ans = 1LL * l.x * r.ans % mod, ans.rans = l.rx + r.rans;
	return ans;
}

void Build(int node = 1, int left = 1, int right = n) {
	if (left == right) {
		st[node].x = x[left - 1];
		st[node].rx = log(x[left - 1]);
		st[node].ry = log(y[left - 1]);
		st[node].y = y[left - 1];
		st[node].ans = 1LL * st[node].x * st[node].y % mod;
		st[node].rans = st[node].rx + st[node].ry;
		return;
	}
	int m = (left + right) / 2;
	Build(2 * node, left, m), Build(2 * node + 1, m + 1, right);
	st[node] = Merge(st[2 * node], st[2 * node + 1]);
}

void Update(int pos, pair<int, int> val, int node = 1, int left = 1, int right = n) {
	if (left == right) {
		if (val.first) {
			st[node].x = val.first;
			st[node].rx = log(val.first);
		}
		else {
			st[node].y = val.second;
			st[node].ry = log(val.second);
		}
		st[node].ans = 1LL * st[node].x * st[node].y % mod;
		st[node].rans = st[node].rx + st[node].ry;
		return;
	}
	int m = (left + right) / 2;
	if (pos <= m)
		Update(pos, val, 2 * node, left, m);
	else
		Update(pos, val, 2 * node + 1, m + 1, right);
	st[node] = Merge(st[2 * node], st[2 * node + 1]);
}


int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; ++i)
		x[i] = X[i], y[i] = Y[i];
	Build();
	return st[1].ans;
}

int updateX(int pos, int val) {
	Update(pos + 1, {val,0});
	return st[1].ans;
}

int updateY(int pos, int val) {
	Update(pos + 1, {0, val});
	return st[1].ans;
}

Compilation message (stderr)

horses.cpp: In function 'node Merge(node, node)':
horses.cpp:16:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  ans.x = 1LL * l.x * r.x % mod;
      |          ~~~~~~~~~~~~~~~~^~~~~
horses.cpp:21:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |   ans.ans = 1LL * l.x * r.ans % mod, ans.rans = l.rx + r.rans;
      |             ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Build(int, int, int)':
horses.cpp:31:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   31 |   st[node].ans = 1LL * st[node].x * st[node].y % mod;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Update(int, std::pair<int, int>, int, int, int)':
horses.cpp:50:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |   st[node].ans = 1LL * st[node].x * st[node].y % mod;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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