Submission #835302

#	Time	Username	Problem	Language	Result	Execution time	Memory
835302		Valaki2	Horses (IOI15_horses)	C++14	100 / 100	524 ms	60532 KiB

horses

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int mod = 1e9 + 7;
const int maxn = 5e5;
const int maxy = 1e9;

int add(int a, int b) {
	return (a + b) % mod;
}

int subt(int a, int b) {
	return (a - b + mod) % mod;
}

int mult(int a, int b) {
	return (a * b) % mod;
}

int power(int a, int b) {
	if(b == 0) {
		return 1ll;
	}
	if(b % 2 == 0) {
		int part = power(a, b / 2);
		return mult(part, part);
	} else {
		return mult(a, power(a, b - 1));
	}
}

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

int divi(int a, int b) {
	return mult(a, inv(b));
}

int n;
int x[1 + maxn], y[1 + maxn];
set<int> big/*s*/;

int tree[1 + maxn];
int segtree[1 + 4 * maxn];

void upd(int pos, int val) {
	while(pos <= n) {
		tree[pos] = mult(tree[pos], val);
		pos += pos & (-pos);
	}
}

int qry(int pos) {
	int res = 1;
	while(pos > 0) {
		res = mult(res, tree[pos]);
		pos -= pos & (-pos);
	}
	return res;
}

void upd_maxi(int v, int vl, int vr, int pos, int val) {
	if(vl == vr) {
		segtree[v] = val;
	} else {
		int mid = (vl + vr) / 2;
		if(pos <= mid) {
			upd_maxi(2 * v, vl, mid, pos, val);
		} else {
			upd_maxi(2 * v + 1, mid + 1, vr, pos, val);
		}
		segtree[v] = max(segtree[2 * v], segtree[2 * v + 1]);
	}
}

int qry_maxi(int v, int vl, int vr, int ql, int qr) {
	if(ql > vr || qr < vl) {
		return 1;
	}
	if(ql == vl && qr == vr) {
		return segtree[v];
	}
	int mid = (vl + vr) / 2;
	return max(qry_maxi(2 * v, vl, mid, ql, min(qr, mid)),
			qry_maxi(2 * v + 1, mid + 1, vr, max(ql, mid + 1), qr));
}

signed calc() {
	int cur_factor = 1, all_factor = 1;
	int prev = n + 1;
	int ans = 0, best = 0;
	for(auto it = big.rbegin(); it != big.rend(); it++) {
		int cur = *it;
	//for(int cur = n; cur >= 1; cur--) { //
		int cur_best_y = qry_maxi(1, 1, n, cur, prev - 1);
		if(cur_best_y > best * cur_factor) {
			best = cur_best_y;
			int cur_pref_x = qry(cur);
			ans = mult(cur_pref_x, cur_best_y);
			cur_factor = 1;
		}
		cur_factor *= x[cur];
		all_factor *= x[cur];
		if(all_factor > maxy) {
			break;
		}
		prev = cur;
	}
	return (signed) ans;
}

signed init(signed N, signed X[], signed Y[]) {
	n = N;
	x[0] = y[0] = 1;
	for(int i = 1; i <= n; i++) {
		x[i] = X[i - 1];
		y[i] = Y[i - 1];
	}
	tree[0] = 1;
	for(int i = 1; i <= n; i++) {
		tree[i] = 1;
	}
	for(int i = 1; i <= n; i++) {
		upd(i, x[i]);
		upd_maxi(1, 1, n, i, y[i]);
	}
	for(int i = 1; i <= n; i++) {
		if(x[i] > 1) {
			big.insert(i);
		}
	}
	big.insert(1);
	return calc();
}

signed updateX(signed pos, signed val) {
	pos++;
	int where = pos, newval = val;
	upd(where, divi(newval, x[where]));
	if(x[where] == 1 && newval > 1) {
		big.insert(where);
	}
	if(x[where] > 1 && newval == 1) {
		big.erase(where);
	}
	big.insert(1);
	x[where] = newval;
	return calc();
}

signed updateY(signed pos, signed val) {
	pos++;
	int where = pos, newval = val;
	y[where] = newval;
	upd_maxi(1, 1, n, where, newval);
	return calc();
}

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