답안 #48142 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48142	2018-05-10T09:06:24 Z	cheater2k	말 (IOI15_horses)	C++17	100 / 100	475 ms	159684 KB

horses

#include "horses.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define double long double
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;
	lz[v] = {0.0, 1};
}

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:18: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:18: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:18: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:18: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<long double, int>&, std::pair<long double, int>)':
horses.cpp:45: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:52: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:76: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:84: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:92: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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	428 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	2 ms	660 KB	Output is correct
6	Correct	2 ms	660 KB	Output is correct
7	Correct	2 ms	660 KB	Output is correct
8	Correct	2 ms	660 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	716 KB	Output is correct
12	Correct	2 ms	716 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	2 ms	716 KB	Output is correct
16	Correct	2 ms	716 KB	Output is correct
17	Correct	2 ms	716 KB	Output is correct
18	Correct	2 ms	716 KB	Output is correct
19	Correct	2 ms	716 KB	Output is correct
20	Correct	2 ms	716 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	716 KB	Output is correct
2	Correct	2 ms	716 KB	Output is correct
3	Correct	2 ms	716 KB	Output is correct
4	Correct	2 ms	716 KB	Output is correct
5	Correct	2 ms	716 KB	Output is correct
6	Correct	2 ms	716 KB	Output is correct
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	2 ms	716 KB	Output is correct
11	Correct	2 ms	716 KB	Output is correct
12	Correct	2 ms	716 KB	Output is correct
13	Correct	2 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	2 ms	748 KB	Output is correct
16	Correct	2 ms	748 KB	Output is correct
17	Correct	2 ms	748 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Correct	2 ms	748 KB	Output is correct
20	Correct	2 ms	748 KB	Output is correct
21	Correct	2 ms	748 KB	Output is correct
22	Correct	2 ms	748 KB	Output is correct
23	Correct	3 ms	764 KB	Output is correct
24	Correct	3 ms	764 KB	Output is correct
25	Correct	3 ms	780 KB	Output is correct
26	Correct	4 ms	836 KB	Output is correct
27	Correct	4 ms	836 KB	Output is correct
28	Correct	3 ms	836 KB	Output is correct
29	Correct	3 ms	836 KB	Output is correct
30	Correct	3 ms	836 KB	Output is correct
31	Correct	3 ms	868 KB	Output is correct
32	Correct	2 ms	868 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	200 ms	84908 KB	Output is correct
2	Correct	442 ms	85036 KB	Output is correct
3	Correct	402 ms	85068 KB	Output is correct
4	Correct	432 ms	85068 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	85068 KB	Output is correct
2	Correct	2 ms	85068 KB	Output is correct
3	Correct	2 ms	85068 KB	Output is correct
4	Correct	2 ms	85068 KB	Output is correct
5	Correct	2 ms	85068 KB	Output is correct
6	Correct	2 ms	85068 KB	Output is correct
7	Correct	2 ms	85068 KB	Output is correct
8	Correct	2 ms	85068 KB	Output is correct
9	Correct	2 ms	85068 KB	Output is correct
10	Correct	2 ms	85068 KB	Output is correct
11	Correct	2 ms	85068 KB	Output is correct
12	Correct	2 ms	85068 KB	Output is correct
13	Correct	2 ms	85068 KB	Output is correct
14	Correct	2 ms	85068 KB	Output is correct
15	Correct	2 ms	85068 KB	Output is correct
16	Correct	2 ms	85068 KB	Output is correct
17	Correct	2 ms	85068 KB	Output is correct
18	Correct	2 ms	85068 KB	Output is correct
19	Correct	2 ms	85068 KB	Output is correct
20	Correct	2 ms	85068 KB	Output is correct
21	Correct	2 ms	85068 KB	Output is correct
22	Correct	2 ms	85068 KB	Output is correct
23	Correct	3 ms	85068 KB	Output is correct
24	Correct	3 ms	85068 KB	Output is correct
25	Correct	3 ms	85068 KB	Output is correct
26	Correct	3 ms	85068 KB	Output is correct
27	Correct	3 ms	85068 KB	Output is correct
28	Correct	3 ms	85068 KB	Output is correct
29	Correct	3 ms	85068 KB	Output is correct
30	Correct	3 ms	85068 KB	Output is correct
31	Correct	3 ms	85068 KB	Output is correct
32	Correct	3 ms	85068 KB	Output is correct
33	Correct	146 ms	85068 KB	Output is correct
34	Correct	140 ms	85068 KB	Output is correct
35	Correct	146 ms	85068 KB	Output is correct
36	Correct	162 ms	85068 KB	Output is correct
37	Correct	115 ms	85068 KB	Output is correct
38	Correct	128 ms	85068 KB	Output is correct
39	Correct	101 ms	85068 KB	Output is correct
40	Correct	130 ms	85068 KB	Output is correct
41	Correct	100 ms	85068 KB	Output is correct
42	Correct	96 ms	85068 KB	Output is correct
43	Correct	112 ms	85068 KB	Output is correct
44	Correct	112 ms	90300 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	90300 KB	Output is correct
2	Correct	2 ms	90300 KB	Output is correct
3	Correct	2 ms	90300 KB	Output is correct
4	Correct	2 ms	90300 KB	Output is correct
5	Correct	2 ms	90300 KB	Output is correct
6	Correct	2 ms	90300 KB	Output is correct
7	Correct	2 ms	90300 KB	Output is correct
8	Correct	2 ms	90300 KB	Output is correct
9	Correct	2 ms	90300 KB	Output is correct
10	Correct	2 ms	90300 KB	Output is correct
11	Correct	2 ms	90300 KB	Output is correct
12	Correct	2 ms	90300 KB	Output is correct
13	Correct	2 ms	90300 KB	Output is correct
14	Correct	2 ms	90300 KB	Output is correct
15	Correct	2 ms	90300 KB	Output is correct
16	Correct	2 ms	90300 KB	Output is correct
17	Correct	2 ms	90300 KB	Output is correct
18	Correct	2 ms	90300 KB	Output is correct
19	Correct	2 ms	90300 KB	Output is correct
20	Correct	2 ms	90300 KB	Output is correct
21	Correct	2 ms	90300 KB	Output is correct
22	Correct	2 ms	90300 KB	Output is correct
23	Correct	3 ms	90300 KB	Output is correct
24	Correct	3 ms	90300 KB	Output is correct
25	Correct	3 ms	90300 KB	Output is correct
26	Correct	3 ms	90300 KB	Output is correct
27	Correct	3 ms	90300 KB	Output is correct
28	Correct	3 ms	90300 KB	Output is correct
29	Correct	3 ms	90300 KB	Output is correct
30	Correct	3 ms	90300 KB	Output is correct
31	Correct	3 ms	90300 KB	Output is correct
32	Correct	3 ms	90300 KB	Output is correct
33	Correct	193 ms	91268 KB	Output is correct
34	Correct	427 ms	91268 KB	Output is correct
35	Correct	381 ms	91292 KB	Output is correct
36	Correct	475 ms	91420 KB	Output is correct
37	Correct	142 ms	91420 KB	Output is correct
38	Correct	139 ms	91420 KB	Output is correct
39	Correct	152 ms	91420 KB	Output is correct
40	Correct	146 ms	91420 KB	Output is correct
41	Correct	113 ms	91420 KB	Output is correct
42	Correct	131 ms	91420 KB	Output is correct
43	Correct	99 ms	91420 KB	Output is correct
44	Correct	135 ms	91420 KB	Output is correct
45	Correct	94 ms	91420 KB	Output is correct
46	Correct	97 ms	91420 KB	Output is correct
47	Correct	116 ms	91420 KB	Output is correct
48	Correct	130 ms	96764 KB	Output is correct
49	Correct	401 ms	102812 KB	Output is correct
50	Correct	400 ms	107740 KB	Output is correct
51	Correct	232 ms	119560 KB	Output is correct
52	Correct	244 ms	131028 KB	Output is correct
53	Correct	325 ms	134456 KB	Output is correct
54	Correct	249 ms	138348 KB	Output is correct
55	Correct	220 ms	140636 KB	Output is correct
56	Correct	275 ms	148156 KB	Output is correct
57	Correct	182 ms	150984 KB	Output is correct
58	Correct	187 ms	154420 KB	Output is correct
59	Correct	113 ms	159684 KB	Output is correct

답안 #48142

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 23.0 / 23.0

Subtask #5 23.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
23.0 / 23.0

Subtask #5
23.0 / 23.0