Submission #1238352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238352		crispxx	Horses (IOI15_horses)	C++20	17 / 100	367 ms	42428 KiB

horses

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define nl '\n'

const int mod = 1e9 + 7;

int binpow(int a, int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = res * 1ll * a % mod;
		a = a * 1ll * a % mod;
		b >>= 1;
	}
	return res;
}

int inv(int a) {
	return binpow(a, mod - 2);
}

struct fenw {
	int n; vector<int> bit;
	
	fenw() {}
	
	fenw(int n) : n(n), bit(n + 1, 1) {}
	
	void update(int i, int x) {
		for(i++; i <= n; i += i & -i) bit[i] = bit[i] * 1ll * x % mod;
	}
	
	int get(int i) {
		int res = 1;
		for(i++; i >= 1; i -= i & -i) res = res * 1ll * bit[i] % mod;
		return res;
	}
};

struct segtree {
	int n; vector<int> t;
	
	segtree() {}
	
	segtree(int n) : n(n), t(n << 2) {}
	
	void update(int v, int l, int r, int i, int x) {
		if(l == r) {
			t[v] = x;
			return;
		}
		int m = (l + r) >> 1;
		if(i <= m) update(v << 1, l, m, i, x);
		else update(v << 1 | 1, m + 1, r, i, x);
		t[v] = max(t[v << 1], t[v << 1 | 1]);
	}
	
	void update(int i, int x) {
		update(1, 0, n - 1, i, x);
	}
	
	int get(int v, int l, int r, int ll, int rr) {
		if(l > rr || ll > r) return 0;
		if(l >= ll && r <= rr) return t[v];
		int m = (l + r) >> 1;
		return max( get(v << 1, l, m, ll, rr), get(v << 1 | 1, m + 1, r, ll, rr) );
	}
	
	int get(int l, int r) {
		return get(1, 0, n - 1, l, r);
	}
};

int n;
vector<int> x, y;

fenw fn;
segtree t;
set<int, greater<>> st;

int get_ans() {
	st.emplace(0);
	
	auto it = st.begin();
	
	int r = *st.begin();
	
	long long mul = x[r], cur_mx = t.get(r, n - 1), cnt = 0;
	
	for(it++; it != st.end() && cnt < 31; it++, cnt++) {
		int l = *it, mx = t.get(l, r - 1);
		
		if(mul * cur_mx < mx) {
			mul = 1;
			cur_mx = mx;
			r = l;
		}
		
		mul *= x[l];
	}
	
	return cur_mx * fn.get(r) % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	
	x.resize(n);
	y.resize(n);
	
	fn = fenw(n);
	t = segtree(n);
	
	for(int i = 0; i < n; i++) {
		x[i] = X[i], y[i] = Y[i];
		fn.update(i, x[i]);
		t.update(i, y[i]);
		
		if(x[i] >= 2) st.emplace(i);
	}
	
	return get_ans();
}

int updateX(int pos, int val) {
	fn.update(pos, inv(x[pos]));
	fn.update(pos, val);
	
	int bsh = x[pos];
	x[pos] = val;
	
	if( (bsh >= 2) == (val >= 2) ) return get_ans();
	
	if(bsh >= 2) st.erase(pos);
	else st.emplace(pos);
	
	return get_ans();
}

int updateY(int pos, int val) {
	t.update(pos, val);
	
	return get_ans();
}

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