Submission #670874

#	Time	Username	Problem	Language	Result	Execution time	Memory
670874		LittleCube	Horses (IOI15_horses)	C++14	100 / 100	179 ms	66648 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll mod = 1'000'000'007;
ll N, x[500005], y[500005];
struct node
{
	ll L = 0, Lmod = 0, R = 0, Rmod = 0, price = 0;
};

ll mul(ll a, ll b)
{
	return min(mod, a * b);
}

node merge(node n, node m)
{
	node ans;
	if (n.price <= min(mod, n.R * m.L) * m.price)
		ans = node{mul(mul(n.L, n.R), m.L),
				   n.Lmod * n.Rmod % mod * m.Lmod % mod,
				   m.R,
				   m.Rmod,
				   m.price};
	else
		ans = node{n.L,
				   n.Lmod,
				   mul(n.R, mul(m.L, m.R)),
				   n.Rmod * m.Lmod % mod * m.Rmod % mod,
				   n.price};
	return ans;
}

node seg[2000005];

void build(ll X[], ll Y[], int i = 1, int L = 0, int R = N - 1)
{
	if (L == R)
		seg[i] = node{X[L], X[L], 1, 1, Y[L]};
	else
	{
		int mid = (L + R) / 2;
		build(X, Y, i << 1, L, mid);
		build(X, Y, i << 1 | 1, mid + 1, R);
		seg[i] = merge(seg[i << 1], seg[i << 1 | 1]);
	}
}

void modify(int pos, ll X, ll Y, int i = 1, int L = 0, int R = N - 1)
{
	if (L == R)
		seg[i] = node{X, X, 1, 1, Y};
	else
	{
		int mid = (L + R) / 2;
		if (pos <= mid)
			modify(pos, X, Y, i << 1, L, mid);
		else
			modify(pos, X, Y, i << 1 | 1, mid + 1, R);
		seg[i] = merge(seg[i << 1], seg[i << 1 | 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(x, y);
	return seg[1].Lmod * seg[1].price % mod;
}

int updateX(int pos, int val)
{
	x[pos] = val;
	modify(pos, x[pos], y[pos]);
	return seg[1].Lmod * seg[1].price % mod;
}

int updateY(int pos, int val)
{
	y[pos] = val;
	modify(pos, x[pos], y[pos]);
	return seg[1].Lmod * seg[1].price % mod;
}

Compilation message (stderr)

horses.cpp:42:60: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 | void build(ll X[], ll Y[], int i = 1, int L = 0, int R = N - 1)
      |                                                          ~~^~~
horses.cpp:55:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 | void modify(int pos, ll X, ll Y, int i = 1, int L = 0, int R = N - 1)
      |                                                                ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:75:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  build(x, y);
      |            ^
horses.cpp:76:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |  return seg[1].Lmod * seg[1].price % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |  modify(pos, x[pos], y[pos]);
      |                            ^
horses.cpp:83:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  return seg[1].Lmod * seg[1].price % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  modify(pos, x[pos], y[pos]);
      |                            ^
horses.cpp:90:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return seg[1].Lmod * seg[1].price % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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