oj.uz

Submission #48140

# Submission time Handle Problem Language Result Execution time Memory
48140 2018-05-10T08:58:31 Z cheater2k Horses (IOI15_horses) C++17
17 / 100
 142 ms 52632 KB 
#include "horses.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 500005;
const int mod = 1e9 + 7;

int n, x[MAXN], y[MAXN];
int prodx[MAXN];
double lgx[MAXN];

int binpow(int a, int b) {
	int ret = 1;
	while(b) {
		if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod;
		b >>= 1;
	}
	return ret;
}

int inverse(int a) {
	return binpow(a, mod - 2);
}

pair <double, int> t[MAXN << 2];
pair <double, int> lz[MAXN << 2];
#define mid ((l + r) >> 1)

void build(int v, int l, int r) {
	lz[v] = {0.0, 1};
	if (l == r) {
		t[v] = {lgx[l] + (double)log(y[l]), 1LL * prodx[l] * y[l] % mod};
		return;
	}
	build(v << 1, l, mid);
	build(v << 1 | 1, mid + 1, r);
	t[v] = max(t[v << 1], t[v << 1 | 1]);
}

void merge(pair<double, int> &p, pair<double, int> q) {
	p.first += q.first;
	p.second = 1LL * p.second * q.second % mod;
}

void push(int v, int l, int r) {
	if (lz[v].second == 1) return;
	if (l < r) merge(lz[v << 1], lz[v]), merge(lz[v << 1 | 1], lz[v]);
	t[v].first += lz[v].first; // log
	t[v].second = 1LL * t[v].second * lz[v].second % mod;
}

void upd(int v, int l, int r, int L, int R, int mul, double lg) {
	push(v, l, r);
	if (R < l || L > r) return;
	if (L <= l && r <= R) {
		lz[v] = {lg, mul}; push(v, l, r); return;
	}
	upd(v << 1, l, mid, L, R, mul, lg);
	upd(v << 1 | 1, mid + 1, r, L, R, mul, lg);
	t[v] = max(t[v << 1], t[v << 1 | 1]);
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; ++i) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	prodx[0] = x[0];
	lgx[0] = log(x[0]);
	for (int i = 1; i < n; ++i) {
		prodx[i] = 1LL * prodx[i - 1] * x[i] % mod;
		lgx[i] = lgx[i - 1] + log(x[i]);
	}
	build(1, 0, n - 1);
	return t[1].second;
}

int updateX(int pos, int val) {
	int mul = 1LL * inverse(x[pos]) * val % mod;
	double lg = -log(x[pos]) + log(val);
	upd(1, 0, n - 1, pos, n - 1, mul, lg);
	x[pos] = val;
	return t[1].second;
}

int updateY(int pos, int val) {
	int mul = 1LL * inverse(y[pos]) * val % mod;
	double lg = -log(y[pos]) + log(val);
	upd(1, 0, n - 1, pos, pos, mul, lg);
	y[pos] = val;
	return t[1].second;
}

Compilation message

horses.cpp: In function 'int binpow(int, int)':
horses.cpp:17:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod;
                    ~~~~~~~~~~~~~~^~~~~
horses.cpp:17:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod;
   ^~
horses.cpp:17:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod;
                                         ^
horses.cpp:17:57: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod;
                                             ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void merge(std::pair<double, int>&, std::pair<double, int>)':
horses.cpp:44:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  p.second = 1LL * p.second * q.second % mod;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void push(int, int, int)':
horses.cpp:51:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  t[v].second = 1LL * t[v].second * lz[v].second % mod;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   prodx[i] = 1LL * prodx[i - 1] * x[i] % mod;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  int mul = 1LL * inverse(x[pos]) * val % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:90:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  int mul = 1LL * inverse(y[pos]) * val % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 772 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 2 ms 780 KB Output is correct
10 Correct 2 ms 872 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 2 ms 876 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 2 ms 876 KB Output is correct
15 Correct 2 ms 876 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 2 ms 876 KB Output is correct
18 Correct 2 ms 876 KB Output is correct
19 Correct 2 ms 876 KB Output is correct
20 Correct 2 ms 876 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 924 KB Output is correct
2 Correct 2 ms 936 KB Output is correct
3 Correct 2 ms 936 KB Output is correct
4 Correct 2 ms 940 KB Output is correct
5 Correct 2 ms 1032 KB Output is correct
6 Correct 2 ms 1032 KB Output is correct
7 Correct 2 ms 1032 KB Output is correct
8 Correct 2 ms 1032 KB Output is correct
9 Correct 2 ms 1032 KB Output is correct
10 Correct 2 ms 1032 KB Output is correct
11 Correct 2 ms 1096 KB Output is correct
12 Correct 2 ms 1096 KB Output is correct
13 Correct 2 ms 1096 KB Output is correct
14 Correct 2 ms 1096 KB Output is correct
15 Correct 2 ms 1096 KB Output is correct
16 Correct 2 ms 1096 KB Output is correct
17 Correct 2 ms 1096 KB Output is correct
18 Correct 3 ms 1096 KB Output is correct
19 Correct 3 ms 1096 KB Output is correct
20 Correct 2 ms 1096 KB Output is correct
21 Incorrect 2 ms 1096 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 52632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 52632 KB Output is correct
2 Correct 2 ms 52632 KB Output is correct
3 Correct 2 ms 52632 KB Output is correct
4 Correct 2 ms 52632 KB Output is correct
5 Correct 2 ms 52632 KB Output is correct
6 Correct 2 ms 52632 KB Output is correct
7 Correct 2 ms 52632 KB Output is correct
8 Correct 2 ms 52632 KB Output is correct
9 Correct 2 ms 52632 KB Output is correct
10 Correct 2 ms 52632 KB Output is correct
11 Correct 2 ms 52632 KB Output is correct
12 Correct 2 ms 52632 KB Output is correct
13 Correct 2 ms 52632 KB Output is correct
14 Correct 2 ms 52632 KB Output is correct
15 Correct 2 ms 52632 KB Output is correct
16 Correct 2 ms 52632 KB Output is correct
17 Correct 2 ms 52632 KB Output is correct
18 Correct 2 ms 52632 KB Output is correct
19 Correct 2 ms 52632 KB Output is correct
20 Correct 2 ms 52632 KB Output is correct
21 Incorrect 2 ms 52632 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 52632 KB Output is correct
2 Correct 2 ms 52632 KB Output is correct
3 Correct 2 ms 52632 KB Output is correct
4 Correct 2 ms 52632 KB Output is correct
5 Correct 2 ms 52632 KB Output is correct
6 Correct 2 ms 52632 KB Output is correct
7 Correct 2 ms 52632 KB Output is correct
8 Correct 2 ms 52632 KB Output is correct
9 Correct 2 ms 52632 KB Output is correct
10 Correct 2 ms 52632 KB Output is correct
11 Correct 2 ms 52632 KB Output is correct
12 Correct 2 ms 52632 KB Output is correct
13 Correct 2 ms 52632 KB Output is correct
14 Correct 2 ms 52632 KB Output is correct
15 Correct 2 ms 52632 KB Output is correct
16 Correct 2 ms 52632 KB Output is correct
17 Correct 2 ms 52632 KB Output is correct
18 Correct 2 ms 52632 KB Output is correct
19 Correct 2 ms 52632 KB Output is correct
20 Correct 2 ms 52632 KB Output is correct
21 Incorrect 2 ms 52632 KB Output isn't correct
22 Halted 0 ms 0 KB -