Submission #819975

#	Time	Username	Problem	Language	Result	Execution time	Memory
819975		Kerim	Horses (IOI15_horses)	C++17	100 / 100	296 ms	101028 KiB

horses

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

const int MAXN = 5e5+5;
const int INF = 1e9+7;
int a[MAXN], b[MAXN], n;
long double pref[MAXN];

struct node{
	int mul;
	int ans;
	long double p;
	node(){
		mul = ans = 0;
		p = 0;
	}
	node(int _mul, int _ans){
		mul = _mul;
		ans = _ans;
	}
}s[MAXN<<2];

node merge(node x, node y){
	node z = node(0, 0);
	if (x.p < y.p)
		z.ans = y.ans, z.p = y.p;
	else
		z.ans = x.ans, z.p = x.p;
	z.mul = (x.mul * 1LL * y.mul) % INF;
	return z;
}

void build(int nd, int x, int y){
	if (x == y){
		s[nd].ans = x;
		s[nd].mul = a[x];
		s[nd].p = pref[x];
		return;
	}
	int mid = (x+y) >> 1;
	build(nd<<1, x, mid);
	build(nd<<1|1, mid+1, y);
	s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}
long double lazy[MAXN<<2];
void shift(int nd){
	long double &ret = lazy[nd];
	lazy[nd<<1] += ret; s[nd<<1].p += ret;
	lazy[nd<<1|1] += ret; s[nd<<1|1].p += ret;
	ret = 0;
}
void inc(int l, int r, long double val, int nd, int x, int y){
	if (l > y or x > r)
		return;
	if (l <= x and y <= r){
		s[nd].p += val;
		lazy[nd] += val;
		return;
	}
	shift(nd);
	int mid = (x+y) >> 1;
	inc(l, r, val, nd<<1, x, mid);
	inc(l, r, val, nd<<1|1, mid+1, y);
	s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}

void upd(int p, long double val, int nd, int x, int y){
	if (x == y){
		s[nd].mul = a[p];
		s[nd].p += val;
		return;
	}
	shift(nd);
	int mid = (x+y) >> 1;
	if (p <= mid)
		upd(p, val, nd<<1, x, mid);
	else	
		upd(p, val, nd<<1|1, mid+1, y);
	s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}

int get(int l, int r, int nd, int x, int y){
	if (l > y or x > r)
		return 1;
	if (l <= x and y <= r)
		return s[nd].mul;
	int mid = (x+y) >> 1;
	return (get(l, r, nd<<1, x, mid) *1LL* get(l, r, nd<<1|1, mid+1, y)) % INF;
}

int ask(int pos){
	return (get(0, pos, 1, 0, n-1) *1LL* b[pos]) % INF;
}

int init(int N, int X[], int Y[]) {
	n = N;
	long double sum = 0;
	for (int i = 0; i < n; i++){
		a[i] = X[i], b[i] = Y[i];
		sum += log(a[i]);
		pref[i] = sum + log(b[i]);
	}
	build(1, 0, n-1);
	return ask(s[1].ans);
}

int updateX(int pos, int val) {	
	inc(pos, n-1, -log(a[pos]) + log(val), 1, 0, n-1);
	a[pos] = val;
	upd(pos, 0, 1, 0, n-1);
	return ask(s[1].ans);
}

int updateY(int pos, int val) {
	upd(pos, log(val) - log(b[pos]), 1, 0, n-1);
	b[pos] = val;
	return ask(s[1].ans);
}

Compilation message (stderr)

horses.cpp: In function 'node merge(node, node)':
horses.cpp:30:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   30 |  z.mul = (x.mul * 1LL * y.mul) % INF;
      |          ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:89:71: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return (get(l, r, nd<<1, x, mid) *1LL* get(l, r, nd<<1|1, mid+1, y)) % INF;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ask(int)':
horses.cpp:93:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |  return (get(0, pos, 1, 0, n-1) *1LL* b[pos]) % INF;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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