Submission #1238315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238315		crispxx	Horses (IOI15_horses)	C++20	54 / 100	166 ms	72848 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;
const double eps = 1e-13;

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 node {
	double val, lazy; int id;
	node() : val(1), lazy(0), id(0) {}
	node(double val, int id) : val(val), id(id) {}
	void merge(node &l, node &r) {
		val = max(l.val, r.val);
		if(val == l.val) id = l.id;
		else id = r.id;
	}
};

struct segtree {
	int n; vector<node> t;
	
	segtree() {}
	
	segtree(vector<double> vals) : n(vals.size()), t(n << 2) {
		build(1, 0, n - 1, vals);
	}
	
	void build(int v, int l, int r, vector<double> &vals) {
		if(l == r) {
			t[v] = node(vals[l], l);
			return;
		}
		int m = (l + r) >> 1;
		build(v << 1, l, m, vals);
		build(v << 1 | 1, m + 1, r, vals);
		t[v].merge(t[v << 1], t[v << 1 | 1]);
	}
	
	void push(int v, int l, int r) {
		if(t[v].lazy == 0) return;
		t[v].val += t[v].lazy;
		if(l != r) {
			t[v << 1].lazy += t[v].lazy;
			t[v << 1 | 1].lazy += t[v].lazy;
		}
		t[v].lazy = 0;
	}
	
	void update(int v, int l, int r, int ll, int rr, double x) {
		push(v, l, r);
		if(l > rr || r < ll) return;
		if(l >= ll && r <= rr) {
			t[v].lazy += x;
			push(v, l, r);
			return;
		}
		int m = (l + r) >> 1;
		update(v << 1, l, m, ll, rr, x);
		update(v << 1 | 1, m + 1, r, ll, rr, x);
		t[v].merge(t[v << 1], t[v << 1 | 1]);
	}
	
	void update(int l, int r, double x) {
		update(1, 0, n - 1, l, r, x);
	}
	
	int get() {
		return t[1].id;
	}
};

int n;
vector<int> x, y;
vector<double> xl, yl;
fenw fn;
segtree t;

int get_ans() {
	int i = t.get();
	return fn.get(i) * 1ll * y[i] % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	
	x.resize(n);
	y.resize(n);
	xl.resize(n);
	yl.resize(n);
	
	vector<double> vals(n);
	double sum = 0;
	
	fn = fenw(n);
	
	for(int i = 0; i < n; i++) {
		x[i] = X[i], y[i] = Y[i];
		xl[i] = log10(X[i]) + eps, yl[i] = log10(Y[i]) + eps;
		sum += xl[i];
		vals[i] = sum + yl[i];
		fn.update(i, x[i]);
	}
	
	t = segtree(vals);
	
	return get_ans();
}

int updateX(int pos, int val) {
	fn.update(pos, inv(x[pos]));
	fn.update(pos, val);
	x[pos] = val;
	
	double lval = log10(val) + eps;
	t.update(pos, n - 1, lval - xl[pos]);
	xl[pos] = lval;
	
	return get_ans();
}

int updateY(int pos, int val) {
	y[pos] = val;
	
	double lval = log10(val) + eps;
	t.update(pos, pos, lval - yl[pos]);
	yl[pos] = lval;
	
	return get_ans();
}

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