Submission #683070

#	Time	Username	Problem	Language	Result	Execution time	Memory
683070		ThegeekKnight16	말 (IOI15_horses)	C++17	17 / 100	131 ms	92464 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;
ll X[MAXN], Y[MAXN];
struct node
{
	ll k, x;
	ll val;
	ll lzK = 1, lzX = -1;

	node(ll KK = 0, ll XX = 0) {k = KK; x = XX; val = ((k * x) % MOD);}

	node operator+(node outro)
	{
		if (val > outro.val) return *this;
		return outro;
	}

} seg[4*MAXN];
int N;

ll exp(ll x, ll y)
{
	if (y == 0) return 1;
	if (y == 1) return x;
	if (y % 2) return ((x * exp(x, y-1)) % MOD);
	else
	{
		ll aux = exp(x, (y / 2));
		return ((aux * aux) % MOD);
	}
}

void refreshK(int pos, int ini, int fim)
{
	if (seg[pos].lzK == 1) return;
	seg[pos].k = ((seg[pos].k * seg[pos].lzK) % MOD);
	seg[pos].val = ((seg[pos].x * seg[pos].k) % MOD);

	if (ini != fim)
	{
		int e = 2*pos; int d = 2*pos + 1;
		seg[e].lzK *= seg[pos].lzK; seg[e].lzK %= MOD;
		seg[d].lzK *= seg[pos].lzK; seg[d].lzK %= MOD;
	}

	seg[pos].lzK = 1;
}

void refreshX(int pos, int ini, int fim)
{
	if (seg[pos].lzX == -1) return;
	seg[pos].x = seg[pos].lzX;
	seg[pos].val = ((seg[pos].k * seg[pos].x) % MOD);

	//Nesse caso, sempre temos que ini == fim

	seg[pos].lzX = -1;
}

void refresh(int pos, int ini, int fim)
{
	refreshK(pos, ini, fim);
	refreshX(pos, ini, fim);
}

void update(int pos, int ini, int fim, int p, int q, ll valK, ll valX)
{
	refresh(pos, ini, fim);
	if (q < ini || p > fim) return;
	if (p <= ini && fim <= q)
	{
		if (valX == -1) seg[pos].lzK = valK;
		else seg[pos].lzX = valX;
		refresh(pos, ini, fim);
		return;
	}
	int m = (ini + fim) >> 1;
	int e = 2*pos; int d = 2*pos + 1;
	update(e, ini, m, p, q, valK, valX);
	update(d, m+1, fim, p, q, valK, valX);
	seg[pos] = seg[e] + seg[d];
}

void build(int pos, int ini, int fim)
{
	if (ini == fim)
	{
		seg[pos] = node(X[ini], Y[ini]);
		return;
	}
	int m = ((ini + fim) >> 1);
	int e = 2*pos; int d = 2*pos + 1;
	build(e, ini, m);
	build(d, m+1, fim);
	seg[pos] = seg[e] + seg[d];
}

int init(int _N, int _X[], int _Y[])
{
	N = _N;
	X[0] = 1;
	for (int i = 1; i <= N; i++) {X[i] = (((long long)(_X[i-1]) * X[i-1]) % MOD); Y[i] = _Y[i-1];}
	build(1, 1, N);


	return (int)(seg[1].val);
}

int updateX(int id, int _val)
{
	id++;
	ll val = (long long)(_val);
	update(1, 1, N, id, N, ((exp(X[id], (MOD-2)) * val) % MOD), -1);
	X[id] = val;

	return (int)(seg[1].val);
}

int updateY(int id, int _val)
{
	id++;
	ll val = (long long)(_val);
	update(1, 1, N, id, id, 1, val);
	Y[id] = val;

	return (int)(seg[1].val);
}

Compilation message (stderr)

horses.cpp: In function 'void refreshX(int, int, int)':
horses.cpp:53:28: warning: unused parameter 'ini' [-Wunused-parameter]
   53 | void refreshX(int pos, int ini, int fim)
      |                        ~~~~^~~
horses.cpp:53:37: warning: unused parameter 'fim' [-Wunused-parameter]
   53 | void refreshX(int pos, int ini, int fim)
      |                                 ~~~~^~~

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