Submission #426353

#	Time	Username	Problem	Language	Result	Execution time	Memory
426353		LastRonin	Horses (IOI15_horses)	C++14	100 / 100	600 ms	143488 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define mp make_pair
#define double long double
using namespace std;

const ll N = 5e5 + 100;
const ll mod = 1e9 + 7;

ll n;
double x[N], y[N], pr[N];


struct seg {
	pair<double, int> t[4 * N];
	double u[4 * N];
	void push(ll v) {
		t[v].f += u[v];
		if(v * 2 + 1 < 4 * N)
			u[v * 2] += u[v],
			u[v * 2 + 1] += u[v];
		u[v] = 0;
	}
	void build(ll v = 1, ll l = 1, ll r = n) {
		if(l == r) {
			t[v].f = pr[l];
			t[v].s = l;
			return;
		}
		ll m = (l + r) >> 1ll;
		build(v * 2, l, m);
		build(v * 2 + 1, m + 1, r);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	void upd(ll l, ll r, double z, ll v = 1, ll tl = 1, ll tr = n) {
		push(v);
		if(l > tr || tl > r)
			return;
		if(l <= tl && tr <= r) {
			u[v] += z;
			push(v);
			return;
		}
		ll m = (tl + tr) >> 1ll;
		upd(l, r, z, v * 2, tl, m);
		upd(l, r, z, v * 2 + 1, m + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
} rt;

struct seg1 {
	ll t[4 * N];
	void upd(ll p, ll z, ll v = 1, ll tl = 1, ll tr = n) {
		if(tl == tr) {
			t[v] = z;
			return;
		}
		ll m = (tl + tr) >> 1ll;
		if(p <= m)
			upd(p, z, v * 2, tl, m);
		else
			upd(p, z, v * 2 + 1, m + 1, tr);
		t[v] = t[v * 2] * t[v * 2 + 1] % mod;					
	}
	ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
		if(l > tr || tl > r)
			return 1ll;
		if(l <= tl && tr <= r)
			return t[v];
		ll m = (tl + tr) >> 1ll;
		return get(l, r, v * 2, tl, m) * get(l, r, v * 2 + 1, m + 1, tr) % mod;
	}
} rt2;

int init(int p, int p2[], int p3[]) {
	n = p;
	for(int i = 1; i <= n; i++)
		x[i] = p2[i - 1], y[i] = p3[i - 1],
		rt2.upd(i, x[i]),
		pr[i] = pr[i - 1] + log(x[i]);
	for(int j = 1; j <= n; j++) {
		pr[j] = pr[j] + log(y[j]);
	}
	rt.build();
	ll z = rt.t[1].s;
	ll ans = rt2.get(1, z) * (ll)y[z] % mod;
	return ans;
}
  
int updateX(int pos, int val) {	
	pos++;
    double lst = x[pos];
	x[pos] = val;
	double za = log(x[pos]) - log(lst);
	rt.upd(pos, n, za);
	rt2.upd(pos, val);
	ll z = rt.t[1].s;
	ll ans = rt2.get(1, z) * (ll)y[z] % mod;
	return ans;
}
int updateY(int pos, int val) {
    pos++;
    double lst = y[pos];
    y[pos] = val;
    double za = log(y[pos]) - log(lst);
    rt.upd(pos, pos, za);
    ll z = rt.t[1].s;
    ll ans = rt2.get(1, z) * (ll)y[z] % mod; 
	return ans;
}

Compilation message (stderr)

horses.cpp: In member function 'void seg::build(long long int, long long int, long long int)':
horses.cpp:30:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   30 |    t[v].s = l;
      |             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:17: warning: conversion from 'long double' to 'long long int' may change value [-Wfloat-conversion]
   82 |   rt2.upd(i, x[i]),
      |              ~~~^
horses.cpp:90:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:102:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:112:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return ans;
      |         ^~~

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