Submission #104996

#	Time	Username	Problem	Language	Result	Execution time	Memory
104996		arman_ferdous	Horses (IOI15_horses)	C++17	100 / 100	643 ms	125816 KiB

horses

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

using ll = long long;
const int N = 5e5+10;
const int MOD = 1e9+7;
const double eps = 1e-9;

int n; ll mulz[N];
double X[N], Y[N];
double lgx[N], lgy[N];
double tmp[N];

struct SGT1{
	struct nude{
		int idx;
		double mx, lazy;
	}t[N<<2];
	void build(int node, int L, int R) {
		t[node].lazy = 0;
		if(L == R) {
			t[node].mx = tmp[L];
			t[node].idx = L;
			return;
		} int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		build(lc, L, mid); build(rc, mid+1, R);

		if(t[lc].mx - t[rc].mx > eps) {
			t[node].mx = t[lc].mx;
			t[node].idx = t[lc].idx;
		} else {
			t[node].mx = t[rc].mx;
			t[node].idx = t[rc].idx;
		}
	}
	void shift(int node) {
		int lc = node<<1, rc = lc|1;
		t[lc].mx += t[node].lazy;
		t[rc].mx += t[node].lazy;
		t[lc].lazy += t[node].lazy;
		t[rc].lazy += t[node].lazy;
		t[node].lazy = 0;

		if(t[lc].mx - t[rc].mx > eps) {
			t[node].mx = t[lc].mx;
			t[node].idx = t[lc].idx;
		} else {
			t[node].mx = t[rc].mx;
			t[node].idx = t[rc].idx;
		}
	}
	void upd(int node, int L, int R, int l, int r, double v) {
		if(r < L || R < l) return;
		if(l <= L && R <= r) {
			t[node].lazy += v;
			t[node].mx += v;
			return;
		} if(fabs(t[node].lazy) > eps) shift(node);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		upd(lc, L, mid, l, r, v);
		upd(rc, mid+1, R, l, r, v);
		if(t[lc].mx - t[rc].mx > eps) {
			t[node].mx = t[lc].mx;
			t[node].idx = t[lc].idx;
		} else {
			t[node].mx = t[rc].mx;
			t[node].idx = t[rc].idx;
		}
	}
	int get() { return t[1].idx; }
}opt;

struct SGT2{
	ll t[N<<2], lazy[N<<2];
	void build(int node, int L, int R) {
		lazy[node] = 1;
		if(L == R) return void(t[node] = mulz[L]);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		build(lc, L, mid); build(rc, mid+1, R);
		t[node] = t[lc] * t[rc] % MOD;
	}
	void shift(int node) {
		int lc = node<<1, rc = lc|1;
		t[lc] = t[lc] * lazy[node] % MOD;
		t[rc] = t[rc] * lazy[node] % MOD;
		lazy[lc] = lazy[lc] * lazy[node] % MOD;
		lazy[rc] = lazy[rc] * lazy[node] % MOD;
		lazy[node] = 1;
	}
	void upd(int node, int L, int R, int l, int r, ll v) {
		if(r < L || R < l) return;
		if(l <= L && R <= r) {
			t[node] = t[node] * v % MOD;
			lazy[node] = lazy[node] * v % MOD;
			return;
		} if(lazy[node] != 1) shift(node);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		upd(lc, L, mid, l, r, v); upd(rc, mid+1, R, l, r, v);
		t[node] = t[lc] * t[rc] % MOD;
	}	
	ll get(int node, int L, int R, int pos) {
		if(L == R) return t[node];
		if(lazy[node] != 1) shift(node);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		if(pos <= mid) return get(lc, L, mid, pos);
		return get(rc, mid+1, R, pos);
	}
}mul;

int init(int _N, int _X[], int _Y[]) {
	n = _N;
	for(int i = 1; i <= n; i++) {
		X[i] = _X[i-1], Y[i] = _Y[i-1];
		lgx[i] = log(X[i]), lgy[i] = log(Y[i]);
	}

	for(int i = 1; i <= n; i++)
		tmp[i] = tmp[i-1] + lgx[i];
	for(int i = 1; i <= n; i++)
		tmp[i] += lgy[i];

	mulz[0] = 1;
	for(int i = 1; i <= n; i++)
		mulz[i] = mulz[i-1] * (ll)X[i] % MOD; 
	for(int i = 1; i <= n; i++)
		mulz[i] = mulz[i] * (ll)Y[i] % MOD;


	opt.build(1,1,n);
	mul.build(1,1,n);
	int idx = opt.get();
	return mul.get(1,1,n,idx);
}

ll powmod(ll a, ll b) {
	ll r = 1;
	while(b) {
		if(b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b>>=1;
	} return r;
}
ll modinv(ll x) { return powmod(x,MOD-2); }

int updateX(int pos, int val) {
	pos++;
	double lg = log((double)val);
	double del = lg - lgx[pos]; 
	opt.upd(1,1,n,pos,n,del);

	ll det = (ll)val * modinv((ll)X[pos]) % MOD;
	mul.upd(1,1,n,pos,n,det);

	X[pos] = val;
	lgx[pos] = lg;
	int idx = opt.get();
	return mul.get(1,1,n,idx);
}

int updateY(int pos, int val) {
	pos++;
	double lg = log((double)val);
	double del = lg - lgy[pos];
	opt.upd(1,1,n,pos,pos,del);

	ll det = (ll)val * modinv((ll)Y[pos]) % MOD;
	mul.upd(1,1,n,pos,pos,det);

	Y[pos] = val;
	lgy[pos] = lg;
	int idx = opt.get();
	return mul.get(1,1,n,idx);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:134:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mul.get(1,1,n,idx);
         ~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:159:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mul.get(1,1,n,idx);
         ~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:174:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mul.get(1,1,n,idx);
         ~~~~~~~^~~~~~~~~~~

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