Submission #571875

#	Time	Username	Problem	Language	Result	Execution time	Memory
571875		kwongweng	Horses (IOI15_horses)	C++17	100 / 100	617 ms	135428 KiB

horses

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

typedef vector<int> vi;
typedef long long ll;
typedef long double ld;

#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ROF(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back

ll MOD = 1000000007;

ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}

vector<ll> x, y;
int n;

struct lol{
	ld val;
	int ind;
	ld add;
};
// range addition and maximum
struct segtree{
	vector<lol> mx;
	int sz;
	void init(int m){
		sz = m;
		mx.assign(4*m, {0,0,0});
	}
	void update(int v, int tl, int tr, int l, int r, ld val){
		if (tl==tr) mx[v].ind = tl;
		if (tl == l && tr == r){
			mx[v].add += val;
			mx[v].val += val;
			return;
		}
		if (l > r) return;
		int tm = (tl + tr)/2;
		update(2*v, tl, tm, l, min(r,tm), val);
		update(2*v+1, tm+1, tr, max(l,tm+1), r, val);
		if (mx[2*v].val + 1e-11 > mx[2*v+1].val){
			mx[v].val = mx[2*v].val + mx[v].add;
			mx[v].ind = mx[2*v].ind;
		}else{
			mx[v].val = mx[2*v+1].val + mx[v].add;
			mx[v].ind = mx[2*v+1].ind;
		}
	}
	void update(int l, int r, ld val){
		update(1,0,sz-1,l,r,val);
	}
	int get(){
		return mx[1].ind;
	}
} st;

// range update point value
struct segtree2{
	vector<ll> prod;
	int sz;
	void init(int m){
		sz = m;
		prod.assign(4*m, 1);
	}
	void update(int v, int tl, int tr, int l, int r, ll val){
		if (l>r) return;
		if (tl==l && tr==r){
			prod[v] *= val;
			prod[v] %= MOD;
			return;
		}
		int tm = (tl+tr)/2;
		update(2*v, tl, tm, l, min(r,tm), val);
		update(2*v+1, tm+1, tr, max(l,tm+1), r, val);
	}
	void update(int l, int r, ll val){
		update(1,0,sz-1,l,r,val);
	}
	ll get(int v, int tl, int tr, int pos){
		if (tl==tr) return prod[v];
		int tm = (tl+tr)/2;
		if (pos <= tm){
			return (get(2*v,tl,tm,pos)*prod[v]) % MOD;
		}else{
			return (get(2*v+1,tm+1,tr,pos)*prod[v]) % MOD;
		}
	}
	ll get(int pos){
		return get(1,0,sz-1,pos);
	}
} st2;

vector<ld> a, b;

int init(int N, int X[], int Y[]) {
	cout << setprecision(12);
	n = N;
	FOR(i,0,n){
		x.pb(X[i]);
		y.pb(Y[i]);
	}
	st.init(N);
	st2.init(N);
	FOR(i,0,N){
		st.update(i,n-1,log(x[i]));
		st.update(i,i,log(y[i]));
		st2.update(i,n-1,x[i]);
	}
	int ans = st.get();
	ll answer = (st2.get(ans) * y[ans]) % MOD;
	return (int) answer;
}

int updateX(int pos, int val) {
	st.update(pos,n-1,log(val)-log(x[pos]));
	ll value = (inverse(x[pos]) * (ll)val) % MOD;
	st2.update(pos,n-1,value);
	x[pos] = val;
	int ans = st.get();
	ll answer = (st2.get(ans) * y[ans]) % MOD;
	return (int) answer;
}

int updateY(int pos, int val) {
	st.update(pos,pos,log(val)-log(y[pos]));
	y[pos] = val;
	int ans = st.get();
	ll answer = (st2.get(ans) * y[ans]) % MOD;
	return (int) answer;
}

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