Submission #132525

#	Time	Username	Problem	Language	Result	Execution time	Memory
132525		antimirage	Horses (IOI15_horses)	C++14	100 / 100	719 ms	126840 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 5e5 + 5, mod = 1e9 + 7;

int a[N], b[N], n;
long long pr[N];

long double pref[N], eps = 1e-13;

struct asd {
	long long val, must;
	long double mx, add;
	
	asd() {
		must = 1;
	}
};

asd t[N * 4];

void build (int v = 1, int tl = 0, int tr = n - 1) {
	if (tl == tr) {
		t[v].val = pr[tl] * 1ll * b[tl] % mod;
		t[v].mx = pref[tl] + log10(b[tl] + eps);
	} else {
		int tm = (tl + tr) >> 1;
		build(v + v, tl, tm);
		build(v + v + 1, tm + 1, tr);
		
		if (t[v + v].mx - t[v + v + 1].mx > eps) {
			t[v].val = t[v + v].val;
			t[v].mx = t[v + v].mx;
		} else {
			t[v].val = t[v + v + 1].val;
			t[v].mx = t[v + v + 1].mx;
		}
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
	
	for (int i = 0; i < n; i++) {
		a[i] = X[i]; b[i] = Y[i];
		pref[i] = (i == 0 ? 0 : pref[i - 1]) + log10(a[i] + eps);
		pr[i] = (i == 0 ? 1 : pr[i - 1]) * 1ll * a[i] % mod;
	}
	build();
	
	return t[1].val;
}
int binpow (int a, int b) {
	if (b == 0)
		return 1;
	if (b & 1)
		return binpow(a, b - 1) * 1ll * a % mod;
		
	int res = binpow(a, b >> 1);
	return res * 1ll * res % mod;
}
void push (int v, int tl, int tr) {
	t[v].mx += t[v].add;
	t[v].val = t[v].val * 1ll * t[v].must % mod;
	if (tl != tr) {
		t[v + v].add += t[v].add;
		t[v + v + 1].add += t[v].add;
		
		t[v + v].must = t[v + v].must * 1ll * t[v].must % mod;
		t[v + v + 1].must = t[v + v + 1].must * 1ll * t[v].must % mod;
	}
	t[v].must = 1;
	t[v].add = 0;
}
void update (int l, int r, long double val, int mult, int v = 1, int tl = 0, int tr = n - 1) {
	push(v, tl, tr);
	if (l > tr || tl > r)
		return;
	if (l <= tl && tr <= r) {
		t[v].add += val;
		t[v].must = t[v].must * 1ll * mult % mod;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) >> 1;
	
	update(l, r, val, mult, v + v, tl, tm);
	update(l, r, val, mult, v + v + 1, tm + 1, tr);
	
	if (t[v + v].mx - t[v + v + 1].mx > eps) {
		t[v].val = t[v + v].val;
		t[v].mx = t[v + v].mx;
	} else {
		t[v].val = t[v + v + 1].val;
		t[v].mx = t[v + v + 1].mx;
	}
}
int updateX(int pos, int val) {
	update(pos, n - 1, -log10(a[pos] + eps), binpow(a[pos], mod - 2) );
	a[pos] = val;
	update(pos, n - 1, log10(a[pos] + eps), a[pos]);
	return t[1].val;
}

int updateY(int pos, int val) {
	update(pos, pos, -log10(b[pos] + eps), binpow(b[pos], mod - 2));
	b[pos] = val;
	update(pos, pos, log10(b[pos] + eps), b[pos]);
	return t[1].val;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:49:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:12:11: note: shadowed declaration is here
 const int N = 5e5 + 5, mod = 1e9 + 7;
           ^
horses.cpp:59:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return t[1].val;
         ~~~~~^~~
horses.cpp: In function 'int binpow(int, int)':
horses.cpp:61:25: warning: declaration of 'b' shadows a global declaration [-Wshadow]
 int binpow (int a, int b) {
                         ^
horses.cpp:14:11: note: shadowed declaration is here
 int a[N], b[N], n;
           ^
horses.cpp:61:25: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 int binpow (int a, int b) {
                         ^
horses.cpp:14:5: note: shadowed declaration is here
 int a[N], b[N], n;
     ^
horses.cpp:65:37: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return binpow(a, b - 1) * 1ll * a % mod;
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:68:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return res * 1ll * res % mod;
         ~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return t[1].val;
         ~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:117:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return t[1].val;
         ~~~~~^~~

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