oj.uz

Submission #54727

# Submission time Handle Problem Language Result Execution time Memory
54727 2018-07-04T19:14:05 Z aome Horses (IOI15_horses) C++17
100 / 100
 375 ms 132720 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

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

#define double long double

int n;
int x[N], y[N];
double val[N];

struct SegmentTree {
	struct Node {
		int pos;
		double val, lazy; 
	};

	Node T1[4 * N];
	int T2[4 * N];

	#define mid ((l + r) >> 1)

	Node merge(Node &x, Node &y) {
		Node z;
		z.lazy = 0;
		if (x.val > y.val) {
			z.pos = x.pos, z.val = x.val; 
		}
		else {
			z.pos = y.pos, z.val = y.val;
		}
		return z;
	}

	void build(int i, int l, int r) {
		T1[i].lazy = 0;
		if (l == r) {
			T1[i].pos = l, T2[i] = x[l];
			T1[i].val = val[l];
			return;
		}
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
		T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
	}

	void push(int i, int l, int r) {
		T1[i].val += T1[i].lazy;
		if (l != r) {
			T1[i << 1].lazy += T1[i].lazy;
			T1[i << 1 | 1].lazy += T1[i].lazy;
		}
		T1[i].lazy = 0;
	}

	void updX(int i, int l, int r, int L, int R, double v) {
		push(i, l, r);
		if (L > r || l > R) return;
		if (L <= l && r <= R) {
			T1[i].lazy = v, push(i, l, r); return;
		}
		updX(i << 1, l, mid, L, R, v);
		updX(i << 1 | 1, mid + 1, r, L, R, v);
		T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
	}

	void updY(int i, int l, int r, int p, int v) {
		push(i, l, r);
		if (p > r || p < l) return;
		if (l == r) {
			double tmp = log(v) - log(y[p]);
			T1[i].val += tmp, y[p] = v;
			return;
		}
		updY(i << 1, l, mid, p, v);
		updY(i << 1 | 1, mid + 1, r, p, v);
		T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
	}

	void updPrd(int i, int l, int r, int p, int v) {
		if (l == r) {
			T2[i] = x[p] = v; return; 
		}
		if (mid >= p) updPrd(i << 1, l, mid, p, v);
		else updPrd(i << 1 | 1, mid + 1, r, p, v);
		T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
	}

	int getPrd(int i, int l, int r, int L, int R) {
		if (l > R || L > r) return 1;
		if (L <= l && r <= R) return T2[i];
		return 1LL * getPrd(i << 1, l, mid, L, R) * getPrd(i << 1 | 1, mid + 1, r, L, R) % mod;
	}

	#undef mid

} IT;

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];
	}
	val[0] = log(x[0]);
	for (int i = 1; i < n; ++i) {
		val[i] = val[i - 1] + log(x[i]);
	}
	for (int i = 0; i < n; ++i) {
		val[i] += log(y[i]);
	}
	IT.build(1, 0, n - 1);
	int opt = IT.T1[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

int updateX(int pos, int val) {
	double tmp = log(val) - log(x[pos]);
	IT.updX(1, 0, n - 1, pos, n - 1, tmp);
	IT.updPrd(1, 0, n - 1, pos, val);
	int opt = IT.T1[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

int updateY(int pos, int val) {
	IT.updY(1, 0, n - 1, pos, val);
	int opt = IT.T1[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

Compilation message

horses.cpp: In member function 'SegmentTree::Node SegmentTree::merge(SegmentTree::Node&, SegmentTree::Node&)':
horses.cpp:27:31: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  Node merge(Node &x, Node &y) {
                               ^
horses.cpp:13:11: note: shadowed declaration is here
 int x[N], y[N];
           ^
horses.cpp:27:31: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  Node merge(Node &x, Node &y) {
                               ^
horses.cpp:13:5: note: shadowed declaration is here
 int x[N], y[N];
     ^
horses.cpp: In member function 'void SegmentTree::build(int, int, int)':
horses.cpp:49:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void SegmentTree::updPrd(int, int, int, int, int)':
horses.cpp:91:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int SegmentTree::getPrd(int, int, int, int, int)':
horses.cpp:97:84: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return 1LL * getPrd(i << 1, l, mid, L, R) * getPrd(i << 1 | 1, mid + 1, r, L, R) % mod;
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:118:55: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:14:8: note: shadowed declaration is here
 double val[N];
        ^~~
horses.cpp:126:55: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:129:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:14:8: note: shadowed declaration is here
 double val[N];
        ^~~
horses.cpp:132:55: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % 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 428 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 520 KB Output is correct
6 Correct 2 ms 520 KB Output is correct
7 Correct 2 ms 520 KB Output is correct
8 Correct 2 ms 536 KB Output is correct
9 Correct 2 ms 536 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 720 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 720 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 720 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 17 ms 764 KB Output is correct
24 Correct 3 ms 764 KB Output is correct
25 Correct 4 ms 780 KB Output is correct
26 Correct 3 ms 864 KB Output is correct
27 Correct 3 ms 864 KB Output is correct
28 Correct 3 ms 864 KB Output is correct
29 Correct 3 ms 864 KB Output is correct
30 Correct 3 ms 864 KB Output is correct
31 Correct 3 ms 864 KB Output is correct
32 Correct 3 ms 864 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 70588 KB Output is correct
2 Correct 349 ms 70716 KB Output is correct
3 Correct 292 ms 70716 KB Output is correct
4 Correct 360 ms 70716 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 70716 KB Output is correct
2 Correct 2 ms 70716 KB Output is correct
3 Correct 2 ms 70716 KB Output is correct
4 Correct 2 ms 70716 KB Output is correct
5 Correct 2 ms 70716 KB Output is correct
6 Correct 2 ms 70716 KB Output is correct
7 Correct 2 ms 70716 KB Output is correct
8 Correct 2 ms 70716 KB Output is correct
9 Correct 2 ms 70716 KB Output is correct
10 Correct 2 ms 70716 KB Output is correct
11 Correct 2 ms 70716 KB Output is correct
12 Correct 2 ms 70716 KB Output is correct
13 Correct 2 ms 70716 KB Output is correct
14 Correct 2 ms 70716 KB Output is correct
15 Correct 2 ms 70716 KB Output is correct
16 Correct 2 ms 70716 KB Output is correct
17 Correct 2 ms 70716 KB Output is correct
18 Correct 2 ms 70716 KB Output is correct
19 Correct 2 ms 70716 KB Output is correct
20 Correct 2 ms 70716 KB Output is correct
21 Correct 2 ms 70716 KB Output is correct
22 Correct 3 ms 70716 KB Output is correct
23 Correct 3 ms 70716 KB Output is correct
24 Correct 3 ms 70716 KB Output is correct
25 Correct 3 ms 70716 KB Output is correct
26 Correct 3 ms 70716 KB Output is correct
27 Correct 3 ms 70716 KB Output is correct
28 Correct 4 ms 70716 KB Output is correct
29 Correct 3 ms 70716 KB Output is correct
30 Correct 4 ms 70716 KB Output is correct
31 Correct 3 ms 70716 KB Output is correct
32 Correct 3 ms 70716 KB Output is correct
33 Correct 123 ms 70716 KB Output is correct
34 Correct 120 ms 70716 KB Output is correct
35 Correct 137 ms 70716 KB Output is correct
36 Correct 139 ms 70716 KB Output is correct
37 Correct 94 ms 70716 KB Output is correct
38 Correct 120 ms 70716 KB Output is correct
39 Correct 86 ms 70716 KB Output is correct
40 Correct 117 ms 70716 KB Output is correct
41 Correct 86 ms 70716 KB Output is correct
42 Correct 88 ms 70716 KB Output is correct
43 Correct 100 ms 70716 KB Output is correct
44 Correct 102 ms 70716 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 70716 KB Output is correct
2 Correct 2 ms 70716 KB Output is correct
3 Correct 2 ms 70716 KB Output is correct
4 Correct 2 ms 70716 KB Output is correct
5 Correct 2 ms 70716 KB Output is correct
6 Correct 2 ms 70716 KB Output is correct
7 Correct 2 ms 70716 KB Output is correct
8 Correct 2 ms 70716 KB Output is correct
9 Correct 2 ms 70716 KB Output is correct
10 Correct 2 ms 70716 KB Output is correct
11 Correct 2 ms 70716 KB Output is correct
12 Correct 2 ms 70716 KB Output is correct
13 Correct 2 ms 70716 KB Output is correct
14 Correct 2 ms 70716 KB Output is correct
15 Correct 2 ms 70716 KB Output is correct
16 Correct 2 ms 70716 KB Output is correct
17 Correct 2 ms 70716 KB Output is correct
18 Correct 2 ms 70716 KB Output is correct
19 Correct 2 ms 70716 KB Output is correct
20 Correct 2 ms 70716 KB Output is correct
21 Correct 2 ms 70716 KB Output is correct
22 Correct 2 ms 70716 KB Output is correct
23 Correct 3 ms 70716 KB Output is correct
24 Correct 3 ms 70716 KB Output is correct
25 Correct 3 ms 70716 KB Output is correct
26 Correct 3 ms 70716 KB Output is correct
27 Correct 3 ms 70716 KB Output is correct
28 Correct 3 ms 70716 KB Output is correct
29 Correct 3 ms 70716 KB Output is correct
30 Correct 3 ms 70716 KB Output is correct
31 Correct 3 ms 70716 KB Output is correct
32 Correct 3 ms 70716 KB Output is correct
33 Correct 199 ms 70716 KB Output is correct
34 Correct 340 ms 70716 KB Output is correct
35 Correct 295 ms 70716 KB Output is correct
36 Correct 354 ms 70716 KB Output is correct
37 Correct 122 ms 70716 KB Output is correct
38 Correct 123 ms 70716 KB Output is correct
39 Correct 147 ms 70716 KB Output is correct
40 Correct 138 ms 70716 KB Output is correct
41 Correct 93 ms 70716 KB Output is correct
42 Correct 113 ms 70716 KB Output is correct
43 Correct 92 ms 70716 KB Output is correct
44 Correct 119 ms 70716 KB Output is correct
45 Correct 87 ms 70716 KB Output is correct
46 Correct 85 ms 70716 KB Output is correct
47 Correct 112 ms 70716 KB Output is correct
48 Correct 105 ms 70716 KB Output is correct
49 Correct 375 ms 75736 KB Output is correct
50 Correct 338 ms 80848 KB Output is correct
51 Correct 269 ms 92776 KB Output is correct
52 Correct 260 ms 104072 KB Output is correct
53 Correct 273 ms 107368 KB Output is correct
54 Correct 282 ms 111372 KB Output is correct
55 Correct 195 ms 113672 KB Output is correct
56 Correct 264 ms 121112 KB Output is correct
57 Correct 199 ms 124028 KB Output is correct
58 Correct 213 ms 127240 KB Output is correct
59 Correct 101 ms 132720 KB Output is correct