oj.uz

Submission #54726

# Submission time Handle Problem Language Result Execution time Memory
54726 2018-07-04T19:06:56 Z aome Horses (IOI15_horses) C++17
54 / 100
 366 ms 66916 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 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 2 ms 544 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 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 2 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 2 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 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
21 Correct 2 ms 720 KB Output is correct
22 Correct 2 ms 720 KB Output is correct
23 Correct 3 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 924 KB Output is correct
26 Correct 3 ms 924 KB Output is correct
27 Correct 3 ms 924 KB Output is correct
28 Correct 3 ms 924 KB Output is correct
29 Correct 3 ms 924 KB Output is correct
30 Correct 3 ms 924 KB Output is correct
31 Correct 3 ms 924 KB Output is correct
32 Correct 3 ms 924 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 66748 KB Output is correct
2 Correct 360 ms 66748 KB Output is correct
3 Correct 313 ms 66876 KB Output is correct
4 Correct 366 ms 66876 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 66876 KB Output is correct
2 Correct 2 ms 66876 KB Output is correct
3 Correct 2 ms 66876 KB Output is correct
4 Correct 2 ms 66876 KB Output is correct
5 Correct 2 ms 66876 KB Output is correct
6 Correct 2 ms 66876 KB Output is correct
7 Correct 2 ms 66876 KB Output is correct
8 Correct 2 ms 66876 KB Output is correct
9 Correct 2 ms 66876 KB Output is correct
10 Correct 2 ms 66876 KB Output is correct
11 Correct 2 ms 66876 KB Output is correct
12 Correct 2 ms 66876 KB Output is correct
13 Correct 2 ms 66876 KB Output is correct
14 Correct 2 ms 66876 KB Output is correct
15 Correct 2 ms 66876 KB Output is correct
16 Correct 2 ms 66876 KB Output is correct
17 Correct 2 ms 66876 KB Output is correct
18 Correct 2 ms 66876 KB Output is correct
19 Correct 2 ms 66876 KB Output is correct
20 Correct 2 ms 66876 KB Output is correct
21 Correct 2 ms 66876 KB Output is correct
22 Correct 2 ms 66876 KB Output is correct
23 Correct 3 ms 66876 KB Output is correct
24 Correct 3 ms 66876 KB Output is correct
25 Correct 3 ms 66876 KB Output is correct
26 Correct 3 ms 66876 KB Output is correct
27 Correct 3 ms 66876 KB Output is correct
28 Correct 3 ms 66876 KB Output is correct
29 Correct 2 ms 66876 KB Output is correct
30 Correct 3 ms 66876 KB Output is correct
31 Correct 3 ms 66876 KB Output is correct
32 Correct 3 ms 66876 KB Output is correct
33 Correct 116 ms 66876 KB Output is correct
34 Correct 116 ms 66876 KB Output is correct
35 Correct 135 ms 66876 KB Output is correct
36 Correct 134 ms 66876 KB Output is correct
37 Correct 88 ms 66876 KB Output is correct
38 Correct 108 ms 66876 KB Output is correct
39 Correct 80 ms 66876 KB Output is correct
40 Correct 110 ms 66876 KB Output is correct
41 Correct 79 ms 66876 KB Output is correct
42 Correct 80 ms 66876 KB Output is correct
43 Correct 96 ms 66876 KB Output is correct
44 Incorrect 98 ms 66876 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 66876 KB Output is correct
2 Correct 2 ms 66876 KB Output is correct
3 Correct 2 ms 66876 KB Output is correct
4 Correct 2 ms 66876 KB Output is correct
5 Correct 2 ms 66876 KB Output is correct
6 Correct 2 ms 66876 KB Output is correct
7 Correct 2 ms 66876 KB Output is correct
8 Correct 2 ms 66876 KB Output is correct
9 Correct 2 ms 66876 KB Output is correct
10 Correct 2 ms 66876 KB Output is correct
11 Correct 2 ms 66876 KB Output is correct
12 Correct 2 ms 66876 KB Output is correct
13 Correct 2 ms 66876 KB Output is correct
14 Correct 2 ms 66876 KB Output is correct
15 Correct 2 ms 66876 KB Output is correct
16 Correct 2 ms 66876 KB Output is correct
17 Correct 2 ms 66876 KB Output is correct
18 Correct 2 ms 66876 KB Output is correct
19 Correct 2 ms 66876 KB Output is correct
20 Correct 2 ms 66876 KB Output is correct
21 Correct 2 ms 66876 KB Output is correct
22 Correct 2 ms 66876 KB Output is correct
23 Correct 3 ms 66876 KB Output is correct
24 Correct 3 ms 66876 KB Output is correct
25 Correct 3 ms 66876 KB Output is correct
26 Correct 3 ms 66876 KB Output is correct
27 Correct 3 ms 66876 KB Output is correct
28 Correct 3 ms 66876 KB Output is correct
29 Correct 2 ms 66876 KB Output is correct
30 Correct 3 ms 66876 KB Output is correct
31 Correct 3 ms 66876 KB Output is correct
32 Correct 3 ms 66876 KB Output is correct
33 Correct 205 ms 66876 KB Output is correct
34 Correct 360 ms 66876 KB Output is correct
35 Correct 292 ms 66916 KB Output is correct
36 Correct 357 ms 66916 KB Output is correct
37 Correct 118 ms 66916 KB Output is correct
38 Correct 114 ms 66916 KB Output is correct
39 Correct 133 ms 66916 KB Output is correct
40 Correct 134 ms 66916 KB Output is correct
41 Correct 87 ms 66916 KB Output is correct
42 Correct 126 ms 66916 KB Output is correct
43 Correct 80 ms 66916 KB Output is correct
44 Correct 113 ms 66916 KB Output is correct
45 Correct 84 ms 66916 KB Output is correct
46 Correct 78 ms 66916 KB Output is correct
47 Correct 99 ms 66916 KB Output is correct
48 Incorrect 95 ms 66916 KB Output isn't correct
49 Halted 0 ms 0 KB -