oj.uz

Submission #965572

# Submission time Handle Problem Language Result Execution time Memory
965572 2024-04-18T23:10:45 Z beaboss Horses (IOI15_horses) C++17
20 / 100
 488 ms 62808 KB 
// 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;
}

bool cmp(pii a, pii b) {
	return (a.f * b.s < b.f * a.s);
}

set<ll> non = {-1};
vi fx, fy;
ll nn;
ll x_prod = 1;
ll solve() {
	non.insert(nn-1);
	ll tot = 1;
	pii frac = {0, 1};
	auto it = prev(non.end(), 2);
	for (; it != non.begin(); it--) {
		// cout << *it << endl;

		if (tot > MOD) break;
		ll rang = query(*it, *next(it, 1)+1);

		// cout << (*it) << ' ' << rang << endl;

		pii here = {rang, tot};
		if (cmp(frac, here)) {
			frac=here;
		}

		tot *= fx[*it];

		// ckmax(mul, (binpow(tot, MOD-2) * rang % MOD));
	}
	// cout << frac.f <<  ' ' << frac.s << endl;
	ll mul = (frac.f * binpow(frac.s, MOD-2) % MOD);
	return x_prod * mul % MOD;
}



ll init(int n, int X[], int 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(int pos, int val) {
	// cout << fx[pos]
	x_prod = (x_prod * binpow(fx[pos], MOD-2)) % MOD;
	if (fx[pos] != 1) non.erase(pos);
	fx[pos]=val;
	// cout << x_prod << endl;
	if (fx[pos] != 1) non.insert(pos);
	x_prod = (x_prod * fx[pos]) % MOD;

	return solve();
}

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


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

// 	cout << init(10, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) << endl;
// // 	cout << updateY(1, 2) << endl;
// // 	cout << updateX(2, 100) << endl;
// // 	cout << updateY(2, 200) << endl;

// }

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4572 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4520 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 54084 KB Output is correct
2 Correct 325 ms 62808 KB Output is correct
3 Correct 313 ms 53844 KB Output is correct
4 Correct 340 ms 57764 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4540 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -