Submission #1282631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282631		Jawad_Akbar_JJ	말 (IOI15_horses)	C++20	17 / 100	1596 ms	30804 KiB

horses

#include <iostream>
#include <set>
#include "horses.h"

using namespace std;
#define ll long long
const int N = 1<<17;
int X[N<<2], Mx[N<<1];
ll prd, mod = 1e9 + 7;
set<int> st;

void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		Mx[cur] = vl;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, vl, lc, st, mid);
	insert(i, vl, rc, mid, en);
	Mx[cur] = max(Mx[lc], Mx[rc]);
}

int get(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return Mx[cur];
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}

int power(int a, int b){
	if (b == 1)
		return a;
	ll ans = power(a, b / 2);
	ans = ans * ans % mod;
	if (b % 2)
		ans = ans * a % mod;
	return ans;
}

int Answer(){
	ll pd = prd, lst = N, sufMax = 0;
	auto it = st.end();

	while (it != begin(st)){
		it =  prev(it);
		pd = pd * power(X[*it], mod - 2) % mod;
		sufMax = max(sufMax, (ll)get(*it, lst)) * X[*it];
		if (sufMax > mod)
			return sufMax % mod * pd;
		lst = *it;
	}
	return sufMax % mod;
}

int init(int n, int x[], int y[]){
	prd = 1;
	for (int i=1;i<=n;i++){
		X[i] = x[i-1];
		prd = prd * X[i] % mod;
		insert(i, y[i-1]);
		if (x[i-1] > 1 or i == 1)
			st.insert(i);
	}

	return Answer();
}

int updateX(int id, int val){
	id++;
	if (X[id] > 1 or id == 1)
		st.erase(id);
	prd = prd * val % mod * power(X[id], mod - 2) % mod;
	X[id] = val;

	if (X[id] > 1 or id == 1)
		st.insert(id);

	return Answer();
}

int updateY(int id, int val){
	id++;
	insert(id, val);

	return Answer();
}

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