oj.uz

답안 #964927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964927 2024-04-17T18:00:14 Z beaboss 말 (IOI15_horses) C++14
0 / 100
 631 ms 51668 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() {
	ll tot = 1;
	pii frac = {0, 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;
		pii here = {rang, tot};
		if (cmp(frac, here)) {
			frac=here;
		}
		// ckmax(mul, (binpow(tot, MOD-2) * rang % MOD));
	}
	ll mul = (frac.f * binpow(frac.s, MOD-2) % MOD);
	// cout << mul << endl;
	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) {
	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(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(3, {2, 1, 3}, {3, 4, 1}) << endl;
// 	cout << updateY(1, 2) << endl;

// }

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 631 ms 51668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -