Submission #1140781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140781		Ekber_Ekber	Horses (IOI15_horses)	C++20	0 / 100	1598 ms	106044 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
#define double long double
using namespace std;

struct point{
	ll ans, sum;
	double lg, anslg;
};

void timelimit() {
	int x = 1e+9;
	while (x--) x++;
}

constexpr ll MAX = 5e+5 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX);
ll n;
vector <ll> a, b;
vector <point> t(4 * MAX);

double log100(ll k) {
	double l = 0.00000001, r = log10(k)+1;
	while (r - l > 0.00000001) {
		double mid = (l + r) / 2;
		double x = pow(10, mid);
		if (x == k) {
			return mid;
		}
		if (x < k) {
			l = mid;
		}
		if (x > k) {
			r = mid;
		}
	}
//	timelimit();
}

void build(ll v, ll tl, ll tr) {
	if (tl == tr) {
		t[v].ans = (a[tl] * b[tl]) % MOD;
		t[v].sum = a[tl] % MOD;
		t[v].lg = log100(a[tl]);
		t[v].anslg = log100(t[v].ans);
		return;
	}
	ll tm = (tl + tr) / 2;
	build(v*2, tl, tm);
	build(v*2+1, tm+1, tr);
	
	t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
	t[v].lg = t[v*2].lg + t[v*2+1].lg;
	if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) {
		t[v].ans = t[v*2].ans;
		t[v].anslg = t[v*2].anslg;
	}
	else {
		t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD;
		t[v].anslg = t[v*2].lg + t[v*2+1].anslg;
	}
}

void updatex(ll v, ll tl, ll tr, ll i, ll x) {
	if (tl == tr) {
		t[v].ans = (x * b[tl]) % MOD;
		t[v].anslg = log100(x) + log100(b[tl]);
		t[v].sum = x;
		t[v].lg = log100(x);
		a[tl] = x;
		return;
	}
	ll tm = (tl + tr) / 2;
	if (i <= tm) {
		updatex(v*2, tl, tm, i, x);
	}
	else {
		updatex(v*2+1, tm+1, tr, i, x);
	}
	t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
	t[v].lg = t[v*2].lg + t[v*2+1].lg;
	
	if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) {
		t[v].ans = t[v*2].ans;
		t[v].anslg = t[v*2].anslg;
	}
	else {
		t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD;
		t[v].anslg = t[v*2].lg + t[v*2+1].anslg;
	}
}

void updatey(ll v, ll tl, ll tr, ll i, ll y) {
	if (tl == tr) {
		t[v].ans = (a[tl] * y) % MOD;
		t[v].anslg = log100(a[tl]) + log100(y);
		b[tl] = y;
		return;
	}
	ll tm = (tl + tr) / 2;
	if (i <= tm) {
		updatey(v*2, tl, tm, i, y);
	}
	else {
		updatey(v*2+1, tm+1, tr, i, y);
	}
	
	t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
	t[v].lg = t[v*2].lg + t[v*2+1].lg;
	if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) {
		t[v].ans = t[v*2].ans;
		t[v].anslg = t[v*2].anslg;
	}
	else {
		t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD;
		t[v].anslg = t[v*2].lg + t[v*2+1].anslg;
	}
}

int init(int N, int X[], int Y[]) {
	n = (ll)N;
	a.clear();
	b.clear();
	for (int i=0; i < N; i++) {
		a.pb(X[i]);
		b.pb(Y[i]);
	}
	build(1, 0, n-1);
	for (int i=0; i < N; i++) {
		X[i] = (int)a[(ll)i];
		Y[i] = (int)b[(ll)i];
	}
	if ((ll)pow(2, t[1].anslg) != t[1].ans) timelimit();
	return t[1].ans;
}

int updateX(int pos, int val) {
	ll i = (ll)pos, x = (ll)val;
	updatex(1, 0, n-1, i, x);
	if ((ll)pow(2, t[1].anslg) != t[1].ans) timelimit();
	return t[1].ans;
}

int updateY(int pos, int val) {
	ll i = (ll)pos, y = (ll)val;
	updatey(1, 0, n-1, i, y);
	return t[1].ans;
}

Compilation message (stderr)

horses.cpp: In function 'long double log100(long long int)':
horses.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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