oj.uz

Submission #54724

# Submission time Handle Problem Language Result Execution time Memory
54724 2018-07-04T18:59:54 Z aome Horses (IOI15_horses) C++17
54 / 100
 417 ms 66968 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

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

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

#define double long double

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) {
			T1[i].val += log(v) - log(y[p]), 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) {
	IT.updX(1, 0, n - 1, pos, n - 1, log(val) - log(x[pos]));
	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:11: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:11: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:90: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:96: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:117: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:120:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:12:8: note: shadowed declaration is here
 double val[N];
        ^~~
horses.cpp:124: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:127:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:12:8: note: shadowed declaration is here
 double val[N];
        ^~~
horses.cpp:130: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 408 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 560 KB Output is correct
11 Correct 2 ms 560 KB Output is correct
12 Correct 2 ms 560 KB Output is correct
13 Correct 2 ms 560 KB Output is correct
14 Correct 3 ms 560 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 3 ms 736 KB Output is correct
17 Correct 3 ms 736 KB Output is correct
18 Correct 3 ms 736 KB Output is correct
19 Correct 2 ms 736 KB Output is correct
20 Correct 2 ms 736 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 736 KB Output is correct
2 Correct 2 ms 736 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 2 ms 736 KB Output is correct
5 Correct 2 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 2 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 736 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 3 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 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 3 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 864 KB Output is correct
24 Correct 3 ms 864 KB Output is correct
25 Correct 4 ms 864 KB Output is correct
26 Correct 3 ms 864 KB Output is correct
27 Correct 4 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 4 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 209 ms 66804 KB Output is correct
2 Correct 417 ms 66840 KB Output is correct
3 Correct 340 ms 66840 KB Output is correct
4 Correct 394 ms 66840 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 66840 KB Output is correct
2 Correct 3 ms 66840 KB Output is correct
3 Correct 2 ms 66840 KB Output is correct
4 Correct 2 ms 66840 KB Output is correct
5 Correct 2 ms 66840 KB Output is correct
6 Correct 2 ms 66840 KB Output is correct
7 Correct 3 ms 66840 KB Output is correct
8 Correct 3 ms 66840 KB Output is correct
9 Correct 3 ms 66840 KB Output is correct
10 Correct 3 ms 66840 KB Output is correct
11 Correct 2 ms 66840 KB Output is correct
12 Correct 2 ms 66840 KB Output is correct
13 Correct 3 ms 66840 KB Output is correct
14 Correct 2 ms 66840 KB Output is correct
15 Correct 2 ms 66840 KB Output is correct
16 Correct 2 ms 66840 KB Output is correct
17 Correct 2 ms 66840 KB Output is correct
18 Correct 2 ms 66840 KB Output is correct
19 Correct 2 ms 66840 KB Output is correct
20 Correct 2 ms 66840 KB Output is correct
21 Correct 2 ms 66840 KB Output is correct
22 Correct 2 ms 66840 KB Output is correct
23 Correct 3 ms 66840 KB Output is correct
24 Correct 5 ms 66840 KB Output is correct
25 Correct 3 ms 66840 KB Output is correct
26 Correct 3 ms 66840 KB Output is correct
27 Correct 3 ms 66840 KB Output is correct
28 Correct 3 ms 66840 KB Output is correct
29 Correct 3 ms 66840 KB Output is correct
30 Correct 4 ms 66840 KB Output is correct
31 Correct 3 ms 66840 KB Output is correct
32 Correct 3 ms 66840 KB Output is correct
33 Correct 118 ms 66840 KB Output is correct
34 Correct 115 ms 66840 KB Output is correct
35 Correct 134 ms 66840 KB Output is correct
36 Correct 146 ms 66840 KB Output is correct
37 Correct 93 ms 66840 KB Output is correct
38 Correct 119 ms 66840 KB Output is correct
39 Correct 88 ms 66840 KB Output is correct
40 Correct 116 ms 66840 KB Output is correct
41 Correct 85 ms 66840 KB Output is correct
42 Correct 91 ms 66840 KB Output is correct
43 Correct 142 ms 66840 KB Output is correct
44 Incorrect 120 ms 66840 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 66840 KB Output is correct
2 Correct 2 ms 66840 KB Output is correct
3 Correct 2 ms 66840 KB Output is correct
4 Correct 2 ms 66840 KB Output is correct
5 Correct 3 ms 66840 KB Output is correct
6 Correct 2 ms 66840 KB Output is correct
7 Correct 2 ms 66840 KB Output is correct
8 Correct 2 ms 66840 KB Output is correct
9 Correct 2 ms 66840 KB Output is correct
10 Correct 2 ms 66840 KB Output is correct
11 Correct 2 ms 66840 KB Output is correct
12 Correct 2 ms 66840 KB Output is correct
13 Correct 2 ms 66840 KB Output is correct
14 Correct 2 ms 66840 KB Output is correct
15 Correct 2 ms 66840 KB Output is correct
16 Correct 2 ms 66840 KB Output is correct
17 Correct 3 ms 66840 KB Output is correct
18 Correct 2 ms 66840 KB Output is correct
19 Correct 2 ms 66840 KB Output is correct
20 Correct 2 ms 66840 KB Output is correct
21 Correct 2 ms 66840 KB Output is correct
22 Correct 2 ms 66840 KB Output is correct
23 Correct 3 ms 66840 KB Output is correct
24 Correct 3 ms 66840 KB Output is correct
25 Correct 3 ms 66840 KB Output is correct
26 Correct 3 ms 66840 KB Output is correct
27 Correct 3 ms 66840 KB Output is correct
28 Correct 3 ms 66840 KB Output is correct
29 Correct 3 ms 66840 KB Output is correct
30 Correct 3 ms 66840 KB Output is correct
31 Correct 3 ms 66840 KB Output is correct
32 Correct 3 ms 66840 KB Output is correct
33 Correct 193 ms 66840 KB Output is correct
34 Correct 334 ms 66840 KB Output is correct
35 Correct 332 ms 66920 KB Output is correct
36 Correct 377 ms 66968 KB Output is correct
37 Correct 120 ms 66968 KB Output is correct
38 Correct 135 ms 66968 KB Output is correct
39 Correct 136 ms 66968 KB Output is correct
40 Correct 134 ms 66968 KB Output is correct
41 Correct 87 ms 66968 KB Output is correct
42 Correct 121 ms 66968 KB Output is correct
43 Correct 81 ms 66968 KB Output is correct
44 Correct 112 ms 66968 KB Output is correct
45 Correct 84 ms 66968 KB Output is correct
46 Correct 80 ms 66968 KB Output is correct
47 Correct 98 ms 66968 KB Output is correct
48 Incorrect 99 ms 66968 KB Output isn't correct
49 Halted 0 ms 0 KB -