Submission #1321607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321607		nagorn_ph	Horses (IOI15_horses)	C++20	100 / 100	732 ms	60880 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define int long long

using namespace std;

const int mod = 1e9 + 7;
const int N = 5e5 + 5;

int n;
int x[N], y[N];
bool inside[N];

struct segtree {
	struct node {
		int val;
		bool exceed;
		node() : val(0), exceed(0) {}
	};
	node seg[4 * N];
	node create(){
		node newnode;
		newnode.val = 1;
		newnode.exceed = 0;
		return newnode;
	}
	node merge(node l, node r){
		node newnode = create();
		newnode.exceed = (l.exceed || r.exceed);
		newnode.val = (l.val * r.val) % mod;
		if ((l.val * r.val) >= mod) newnode.exceed = true;
		return newnode;
	}
	void build(int l, int r, int i){
		if (l == r) return seg[i].val = x[l], void();
		int mid = (l + r) / 2;
		build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
		seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
	}
	void update(int l, int r, int i, int idx, int val){
		if (l == r) return seg[i].val = val, void();
		int mid = (l + r) / 2;
		if (idx <= mid) update(l, mid, 2 * i, idx, val);
		else update(mid + 1, r, 2 * i + 1, idx, val);
		seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
	}
	node query(int l, int r, int i, int ll, int rr){
		if (l >= ll && r <= rr) return seg[i];
		if (r < ll || l > rr) return create();
		int mid = (l + r) / 2;
		return merge(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
	}
} seg;

struct indexmaintain {
	int seg[4 * N];
	void build(int l, int r, int i){
		if (l == r) return seg[i] = (x[l] > 1), void();
		int mid = (l + r) / 2;
		build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
		seg[i] = seg[2 * i] + seg[2 * i + 1];
	}
	void update(int l, int r, int i, int idx, int val){
		if (l == r) return seg[i] = (val > 1), void();
		int mid = (l + r) / 2;
		if (idx <= mid) update(l, mid, 2 * i, idx, val);
		else update(mid + 1, r, 2 * i + 1, idx, val);
		seg[i] = seg[2 * i] + seg[2 * i + 1];
	}
	int query(int l, int r, int i, int k){
		if (l == r) return l;
		int mid = (l + r) / 2;
		if (seg[2 * i + 1] >= k) return query(mid + 1, r, 2 * i + 1, k);
		else return query(l, mid, 2 * i, k - seg[2 * i + 1]);
	}
} indices;

struct mxseg{
	int seg[4 * N];
	void build(int l, int r, int i){
		if (l == r) return seg[i] = y[l], void();
		int mid = (l + r) / 2;
		build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
		seg[i] = max(seg[2 * i], seg[2 * i + 1]);
	}
	void update(int l, int r, int i, int idx, int val){
		if (l == r) return seg[i] = val, void();
		int mid = (l + r) / 2;
		if (idx <= mid) update(l, mid, 2 * i, idx, val);
		else update(mid + 1, r, 2 * i + 1, idx, val);
		seg[i] = max(seg[2 * i], seg[2 * i + 1]);
	}
	int query(int l, int r, int i, int ll, int rr){
		if (l >= ll && r <= rr) return seg[i];
		if (r < ll || l > rr) return 0;
		int mid = (l + r) / 2;
		return max(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
	}
} mxx;

int query(){
	int st = 1, exact = indices.seg[1];
	for (int i = 1; i <= indices.seg[1]; i++) {
		int idx = indices.query(1, n, 1, i);
		// cout << i << ": " << idx << ": " << seg.query(1, n, 1, idx, n).exceed << "\n";
		if (seg.query(1, n, 1, idx, n).exceed) {
			st = idx;
			exact = i;
			break;
		}
	}
	if (indices.seg[1] == 0) return mxx.query(1, n, 1, 1, n);
	long double mx = 0;
	long double prod = 1.0;
	int num = 1, prodmod = 1;
	int fst = indices.query(1, n, 1, exact);
	if (st < fst) {
		int val = mxx.query(1, n, 1, st, fst - 1);
		mx = val;
		num = val % mod;
	}
	for (int i = exact; i >= 1; i--) {
		int idx = indices.query(1, n, 1, i);
		prod *= x[idx];
		prodmod = (prodmod * x[idx]) % mod;
		int nxt = (i == 1 ? n + 1 : indices.query(1, n, 1, i - 1));
		int mxy = mxx.query(1, n, 1, idx, nxt - 1);
		if (prod * mxy > mx) {
			mx = prod * mxy;
			num = (prodmod * mxy) % mod;
		}
	}
	int answer = ((seg.query(1, n, 1, 1, st - 1).val * num) % mod);
	return answer;
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
	n = N;
	for (int i = 0; i < n; i++) x[i + 1] = X[i];
	for (int i = 0; i < n; i++) y[i + 1] = Y[i];
	y[0] = 1;
	seg.build(1, n, 1);
	indices.build(1, n, 1);
	mxx.build(1, n, 1);
	return query();
}

int32_t updateX(int32_t pos, int32_t val) {	
	++pos;
	x[pos] = val;
	seg.update(1, n, 1, pos, val);
	indices.update(1, n, 1, pos, val);
	return query();
}

int32_t updateY(int32_t pos, int32_t val) {
	++pos;
	y[pos] = val;
	mxx.update(1, n, 1, pos, val);
	return query();
}

// int32_t main(){
// 	int32_t n; cin >> n;
// 	int32_t x[n], y[n];
// 	for (int i = 0; i < n; i++) cin >> x[i];
// 	for (int i = 0; i < n; i++) cin >> y[i];
// 	cout << init(n, x, y) << "\n";
// 	int32_t m; cin >> m;
// 	while (m--) {
// 		int t; cin >> t;
// 		int pos, val; cin >> pos >> val;
// 		if (t == 1) cout << updateX(pos, val) << "\n";
// 		else cout << updateY(pos, val) << "\n";
// 	}
// }

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