Submission #513768

#	Time	Username	Problem	Language	Result	Execution time	Memory
513768		sliviu	Horses (IOI15_horses)	C++14	0 / 100	137 ms	46272 KiB

horses

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

using namespace std;

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

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

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

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

int pow(int b, int e) {
	int ans = 1;
	while (e) {
		if (e & 1)
			ans = 1LL * ans * b % mod;
		b = 1LL * b * b % mod, e >>= 1;
	}
	return ans;
}

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) {
	curinv = pow(x[pos], mod - 2);
	Update({val,0}, ++pos);
	return 1LL*st[1].ans*st[1].x%mod;
}

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

Compilation message (stderr)

horses.cpp: In function 'void Build(int, int, int)':
horses.cpp:17:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |   st[node].x = (curx = (1LL * curx * x[left - 1]) % mod);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:26:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   26 |   st[node].ans = 1LL * st[2 * node].ans * st[2 * node].x % mod, st[node].rans = st[2 * node].rans + st[2 * node].rx;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:28:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   28 |   st[node].ans = 1LL * st[2 * node + 1].ans * st[2 * node + 1].x % mod, st[node].rans = st[2 * node + 1].rans + st[2 * node + 1].rx;;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Update(std::pair<int, int>, int, int, int, int, int)':
horses.cpp:34:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |    st[node].x = 1LL * st[node].x * val.first % mod * curinv % mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:50:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |   st[node].ans = 1LL * st[2 * node].ans * st[2 * node].x % mod, st[node].rans = st[2 * node].rans + st[2 * node].rx;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:52:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   52 |   st[node].ans = 1LL * st[2 * node + 1].ans * st[2 * node + 1].x % mod, st[node].rans = st[2 * node + 1].rans + st[2 * node + 1].rx;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int pow(int, int)':
horses.cpp:59:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   59 |    ans = 1LL * ans * b % mod;
      |          ~~~~~~~~~~~~~~^~~~~
horses.cpp:60:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |   b = 1LL * b * b % mod, e >>= 1;
      |       ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:76:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |  return 1LL*st[1].ans*st[1].x%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:81:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |  return 1LL * st[1].ans * st[1].x % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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