Submission #342811

#	Time	Username	Problem	Language	Result	Execution time	Memory
342811		monus1042	Horses (IOI15_horses)	C++17	100 / 100	720 ms	131504 KiB

horses

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

typedef unsigned long long ll;
typedef pair<int,int> ii;
typedef long double ld;

const ll MOD = 1000000007;
const int MAXS = 5e5+10;
int n;
vector<ll> x, y;
vector<ld> accbasis;
vector<pair<ld, int>> seg(MAXS * 4);
vector<ld> lazy(MAXS *4);
vector<ll> fen(MAXS, 1LL); // using 1 indexing in this

ll power(ll b, ll exp){
	if (exp == 0) return 1LL;
	if (exp&1) return (power((b*b) % MOD, exp/2) * b) % MOD;
	return power((b*b)%MOD, exp/2) % MOD;
}

void build(int node, int l, int r){
	if (l == r){
		seg[node] = make_pair(accbasis[l], l);
		return;
	}
	int mid = (l + r) / 2;
	build(node *2, l, mid);
	build(node*2 +1, mid+1, r);
	if (seg[node*2].first > seg[node*2+1].first) seg[node] = seg[node*2];
	else seg[node] = seg[node*2+1];
}

void update(int node, int l, int r, int xl, int xr, ld delta){
	if (lazy[node] != 0.0){
		seg[node].first += lazy[node];
		if (l!=r){
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0.0;
	}
	if (l > xr || r < xl) return;
	if (xl <= l && r <= xr){
		seg[node].first += delta;
		if (l != r){
			lazy[node*2] += delta;
			lazy[node*2+1] += delta;
		}
		return;
	}
	int mid = (l+r)/2;
	update(node*2, l, mid, xl, xr, delta);
	update(node*2+1, mid+1, r, xl, xr, delta);
	if (seg[node*2].first > seg[node*2+1].first) seg[node] = seg[node*2];
	else seg[node] = seg[node*2+1];
}

void upd(int pos, ll factor){
	while(pos <= n){
		fen[pos] = (fen[pos] * factor) % MOD;
		pos += pos&-pos;
	}
}

ll que(int pos){
	ll answer = 1LL;
	while(pos){
		answer = (answer * fen[pos]) % MOD;
		pos -= pos&-pos;
	}
	return answer;
}

int solve(){
	int position = seg[1].second + 1;
	ll answer = (que(position) * y[position-1]) % MOD;
	return (int)answer;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i=0; i<n; i++) x.push_back(X[i]), y.push_back(Y[i]);
	ld acc = 0.0;
	for (int i=0; i<n; i++){
		acc = acc + (ld)log10(x[i]);
		accbasis.push_back(acc);
		upd(i+1, x[i]);
	}
	build(1, 0, n-1);
	for (int i=0; i<n; i++){
		update(1, 0, n-1, i, i, (ld)log10(y[i]));
	}
	return solve();
}

int updateX(int pos, int val) {
	ll inv = power(x[pos], MOD-2);
	upd(pos+1, inv);
	upd(pos+1, (ll)val);
	ld delta = (ld)log10(val) - (ld)log10(x[pos]);
	update(1, 0, n-1, pos, n-1, delta);
	x[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	ld delta = (ld)log10(val) - log10(y[pos]);
	update(1, 0, n-1, pos, pos, delta);
	y[pos] = val;
	return solve();
}

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