Submission #587504

#	Time	Username	Problem	Language	Result	Execution time	Memory
587504		benson1029	Horses (IOI15_horses)	C++14	100 / 100	525 ms	74792 KiB

horses

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

long long mod = 1e9+7;
long double seglog[2000005];
long long segmul[2000005];
long double lzylog[2000005];
long long lzymul[2000005];
int n;
long long x[500005], y[500005];

long long fpw(long long n, long long p) {
	if(p==0) return 1LL;
	long long t = fpw(n, p/2);
	t = (t*t) % mod;
	if(p%2) t = (t*n) % mod;
	return t;
}

long long inv(long long n) {
	return fpw(n, mod-2);
}

void push(int x) {
	seglog[x*2] += lzylog[x];
	seglog[x*2+1] += lzylog[x];
	lzylog[x*2] += lzylog[x];
	lzylog[x*2+1] += lzylog[x];
	lzylog[x] = 0;
	segmul[x*2] = (segmul[x*2] * lzymul[x]) % mod;
	segmul[x*2+1] = (segmul[x*2+1] * lzymul[x]) % mod;
	lzymul[x*2] = (lzymul[x*2] * lzymul[x]) % mod;
	lzymul[x*2+1] = (lzymul[x*2+1] * lzymul[x]) % mod;
	lzymul[x] = 1;
}

void seg_set(int x, int l, int r, int pos, int val, long double LOG) {
	if(l==r) {
		segmul[x] = val;
		seglog[x] = LOG;
	} else {
		if(pos <= (l+r)/2) seg_set(x*2, l, (l+r)/2, pos, val, LOG);
		else seg_set(x*2+1, (l+r)/2+1, r, pos, val, LOG);
		if(seglog[x*2] > seglog[x*2+1]) {
			seglog[x] = seglog[x*2];
			segmul[x] = segmul[x*2];
		} else {
			seglog[x] = seglog[x*2+1];
			segmul[x] = segmul[x*2+1];
		}
	}
}

void seg_upd(int x, int l, int r, int ll, int rr, long long val, long double LOG) {
	if(l!=r) push(x);
	if(ll <= l && r <= rr) {
		seglog[x] += LOG;
		segmul[x] = (segmul[x] * val) % mod;
		lzylog[x] += LOG;
		lzymul[x] = (lzymul[x] * val) % mod;
	} else if(l > rr || r < ll) {

	} else {
		seg_upd(x*2, l, (l+r)/2, ll, rr, val, LOG);
		seg_upd(x*2+1, (l+r)/2+1, r, ll, rr, val, LOG);
		if(seglog[x*2] > seglog[x*2+1]) {
			seglog[x] = seglog[x*2];
			segmul[x] = segmul[x*2];
		} else {
			seglog[x] = seglog[x*2+1];
			segmul[x] = segmul[x*2+1];
		}
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0; i<4*n; i++) lzymul[i] = 1;
	long double logc = 0; long long mulc = 1;
	for(int i=0; i<N; i++) {
		x[i] = X[i]; y[i] = Y[i];
		mulc = (mulc * X[i]) % mod;
		logc += log(X[i]);
		seg_set(1, 0, n-1, i, (mulc * Y[i]) % mod, logc + log(Y[i]));
	}
	return segmul[1];
}

int updateX(int pos, int val) {	
	long long v = (inv(x[pos]) * val) % mod;
	long double t = log(val) - log(x[pos]);
	seg_upd(1, 0, n-1, pos, n-1, v, t);
	x[pos] = val;
	return segmul[1];
}

int updateY(int pos, int val) {
	long long v = (inv(y[pos]) * val) % mod;
	long double t = log(val) - log(y[pos]);
	seg_upd(1, 0, n-1, pos, pos, v, t);
	y[pos] = val;
	return segmul[1];
}

Compilation message (stderr)

horses.cpp: In function 'long long int fpw(long long int, long long int)':
horses.cpp:13:25: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   13 | long long fpw(long long n, long long p) {
      |               ~~~~~~~~~~^
horses.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^
horses.cpp: In function 'long long int inv(long long int)':
horses.cpp:21:25: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   21 | long long inv(long long n) {
      |               ~~~~~~~~~~^
horses.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^
horses.cpp: In function 'void push(int)':
horses.cpp:25:15: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   25 | void push(int x) {
      |           ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
   11 | long long x[500005], y[500005];
      |           ^
horses.cpp: In function 'void seg_set(int, int, int, int, int, long double)':
horses.cpp:38:18: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   38 | void seg_set(int x, int l, int r, int pos, int val, long double LOG) {
      |              ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
   11 | long long x[500005], y[500005];
      |           ^
horses.cpp: In function 'void seg_upd(int, int, int, int, int, long long int, long double)':
horses.cpp:55:18: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   55 | void seg_upd(int x, int l, int r, int ll, int rr, long long val, long double LOG) {
      |              ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
   11 | long long x[500005], y[500005];
      |           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |   seg_set(1, 0, n-1, i, (mulc * Y[i]) % mod, logc + log(Y[i]));
      |                         ~~~~~~~~~~~~~~^~~~~
horses.cpp:87:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |  return segmul[1];
      |         ~~~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:95:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |  return segmul[1];
      |         ~~~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  return segmul[1];
      |         ~~~~~~~~^

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