Submission #964922

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964922	2024-04-17T17:52:52 Z	beaboss	Horses (IOI15_horses)	C++14	Compilation error	0 ms	0 KB

horses

// Source: https://oj.uz/problem/view/IOI15_horses
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

const ll N = 5e5 + 10;
const ll MOD = 1e9 + 7;
#define lc i << 1
#define rc (i << 1) + 1



ll binpow(ll x, ll n) { // x ^ n
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = (res * x) % MOD;
		x = (x * x) % MOD;
		n/=2;
	}
	return res;
}

ll st[4 * N];


void up(ll i) {
	st[i] = max(st[lc], st[rc]);
}

void update(ll ind, ll val, ll i = 1, ll l = 0, ll r = N) {
	// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
	// cout << l << r << st[i] << endl;
	if (r == l) return;
	if (r-1 == l && l == ind) {
		st[i] = val;
		return;
	}
	if (r-1 == l) return;


	ll m = (l + r) / 2;
	if (ind < m) update(ind, val, lc, l, m);
	if (m <= ind) update(ind, val, rc, m, r);

	up(i);
	// cout << l << r << ' ' << st[i] << endl;


}

ll query(ll ql, ll qr, ll i = 1, ll l = 0, ll r = N) {
	// cout << i << endl;
	if (r == l) return 0;

	if (ql <= l && r <= qr) {
		// cout << ql << qr << ' ' << l << ' ' << r << ' ' << st[i] << endl;

		return st[i];
	}

	if (r == l+1) return 0;

	ll m = (l + r) / 2;
	ll res = 0;
	if (ql <= m) ckmax(res, query(ql, qr, lc, l, m));
	if (qr >= m) ckmax(res, query(ql, qr, rc,  m, r));
	return res;
}



set<ll> non = {-1};
vi fx, fy;
ll nn;
ll x_prod = 1;
ll solve() {
	ll tot = 1;
	ll mul = 1;
	auto it = prev(non.end(), 2);
	for (; it != non.begin(); it--) {
		// cout << *it << endl;
		tot *= fy[*it];
		if (tot > MOD) break;
		ll rang = query(*it, *next(it, 1)+1);
		// cout << rang << tot << endl;
		ckmax(mul, (binpow(tot, MOD-2) * rang % MOD));
	}
	// cout << mul << endl;
	return x_prod * mul % MOD;
}



ll init(ll n, vi X, vi Y) {
	nn = n;
	non.insert(n + 1);
	vi x(n), y(n);
	x_prod = 1;
	FOR(i, 0, n) {
		x[i] = X[i];
		y[i] = Y[i];
		if (x[i] != 1) non.insert(i);
		update(i, y[i]);
		x_prod = (x_prod * x[i]) % MOD;
	}
	fx = x, fy = y;
	
		


	// cout << query(0, 10) << endl;
	// return 0;
	return solve();
}

ll updateX(ll pos, ll val) {
	x_prod = (x_prod * binpow(fx[pos], MOD-2)) % MOD;
	if (fx[pos] != 1) non.erase(pos);
	fx[pos]=val;
	if (fx[pos] != 1) non.insert(pos);
	x_prod = (x_prod * fx[pos]) % MOD;
	return solve();
}

ll updateY(ll pos, ll val) {
	fy[pos]=val;
	update(pos, fy[pos]);
	return solve();
}


// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	cout << init(3, {2, 1, 3}, {3, 4, 1}) << endl;
// 	cout << updateY(1, 2) << endl;

// }

Compilation message

/usr/bin/ld: /tmp/cct4gbVQ.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x113): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x16d): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status