oj.uz

Submission #54722

# Submission time Handle Problem Language Result Execution time Memory
54722 2018-07-04T18:59:15 Z aome Horses (IOI15_horses) C++17
54 / 100
 246 ms 200228 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];

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:25: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:25: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:47: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:88: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:94: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:115: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:118: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:122: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:125: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:128: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 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 612 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct
13 Correct 2 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 676 KB Output is correct
17 Correct 2 ms 676 KB Output is correct
18 Correct 2 ms 676 KB Output is correct
19 Correct 2 ms 676 KB Output is correct
20 Correct 2 ms 676 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 676 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 3 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct
13 Correct 2 ms 676 KB Output is correct
14 Correct 2 ms 676 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 3 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 3 ms 748 KB Output is correct
23 Correct 3 ms 748 KB Output is correct
24 Correct 3 ms 764 KB Output is correct
25 Correct 3 ms 832 KB Output is correct
26 Correct 3 ms 912 KB Output is correct
27 Correct 2 ms 924 KB Output is correct
28 Correct 2 ms 932 KB Output is correct
29 Correct 2 ms 932 KB Output is correct
30 Correct 3 ms 984 KB Output is correct
31 Correct 3 ms 1052 KB Output is correct
32 Correct 3 ms 1052 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 42300 KB Output is correct
2 Correct 227 ms 42320 KB Output is correct
3 Correct 188 ms 46156 KB Output is correct
4 Correct 246 ms 53828 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 53828 KB Output is correct
2 Correct 2 ms 53828 KB Output is correct
3 Correct 2 ms 53828 KB Output is correct
4 Correct 3 ms 53828 KB Output is correct
5 Correct 2 ms 53828 KB Output is correct
6 Correct 2 ms 53828 KB Output is correct
7 Correct 2 ms 53828 KB Output is correct
8 Correct 2 ms 53828 KB Output is correct
9 Correct 2 ms 53828 KB Output is correct
10 Correct 2 ms 53828 KB Output is correct
11 Correct 2 ms 53828 KB Output is correct
12 Correct 2 ms 53828 KB Output is correct
13 Correct 2 ms 53828 KB Output is correct
14 Correct 2 ms 53828 KB Output is correct
15 Correct 2 ms 53828 KB Output is correct
16 Correct 2 ms 53828 KB Output is correct
17 Correct 2 ms 53828 KB Output is correct
18 Correct 2 ms 53828 KB Output is correct
19 Correct 2 ms 53828 KB Output is correct
20 Correct 2 ms 53828 KB Output is correct
21 Correct 2 ms 53828 KB Output is correct
22 Correct 2 ms 53828 KB Output is correct
23 Correct 3 ms 53828 KB Output is correct
24 Correct 3 ms 53828 KB Output is correct
25 Correct 3 ms 53828 KB Output is correct
26 Correct 4 ms 53828 KB Output is correct
27 Correct 3 ms 53828 KB Output is correct
28 Correct 2 ms 53828 KB Output is correct
29 Correct 3 ms 53828 KB Output is correct
30 Correct 4 ms 53828 KB Output is correct
31 Correct 3 ms 53828 KB Output is correct
32 Correct 2 ms 53828 KB Output is correct
33 Correct 86 ms 56988 KB Output is correct
34 Correct 90 ms 60936 KB Output is correct
35 Correct 119 ms 71828 KB Output is correct
36 Correct 110 ms 82764 KB Output is correct
37 Correct 60 ms 84800 KB Output is correct
38 Correct 98 ms 87780 KB Output is correct
39 Correct 56 ms 89784 KB Output is correct
40 Correct 87 ms 95736 KB Output is correct
41 Correct 58 ms 97768 KB Output is correct
42 Correct 58 ms 99860 KB Output is correct
43 Correct 78 ms 106232 KB Output is correct
44 Incorrect 77 ms 112652 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 112652 KB Output is correct
2 Correct 2 ms 112652 KB Output is correct
3 Correct 2 ms 112652 KB Output is correct
4 Correct 2 ms 112652 KB Output is correct
5 Correct 2 ms 112652 KB Output is correct
6 Correct 2 ms 112652 KB Output is correct
7 Correct 2 ms 112652 KB Output is correct
8 Correct 2 ms 112652 KB Output is correct
9 Correct 2 ms 112652 KB Output is correct
10 Correct 2 ms 112652 KB Output is correct
11 Correct 2 ms 112652 KB Output is correct
12 Correct 2 ms 112652 KB Output is correct
13 Correct 2 ms 112652 KB Output is correct
14 Correct 2 ms 112652 KB Output is correct
15 Correct 2 ms 112652 KB Output is correct
16 Correct 2 ms 112652 KB Output is correct
17 Correct 2 ms 112652 KB Output is correct
18 Correct 2 ms 112652 KB Output is correct
19 Correct 2 ms 112652 KB Output is correct
20 Correct 2 ms 112652 KB Output is correct
21 Correct 2 ms 112652 KB Output is correct
22 Correct 2 ms 112652 KB Output is correct
23 Correct 2 ms 112652 KB Output is correct
24 Correct 3 ms 112652 KB Output is correct
25 Correct 3 ms 112652 KB Output is correct
26 Correct 3 ms 112652 KB Output is correct
27 Correct 3 ms 112652 KB Output is correct
28 Correct 3 ms 112652 KB Output is correct
29 Correct 2 ms 112652 KB Output is correct
30 Correct 3 ms 112652 KB Output is correct
31 Correct 3 ms 112652 KB Output is correct
32 Correct 3 ms 112652 KB Output is correct
33 Correct 124 ms 117656 KB Output is correct
34 Correct 231 ms 130260 KB Output is correct
35 Correct 182 ms 134056 KB Output is correct
36 Correct 226 ms 141688 KB Output is correct
37 Correct 86 ms 144832 KB Output is correct
38 Correct 84 ms 148676 KB Output is correct
39 Correct 115 ms 159464 KB Output is correct
40 Correct 111 ms 170368 KB Output is correct
41 Correct 59 ms 172372 KB Output is correct
42 Correct 80 ms 175496 KB Output is correct
43 Correct 56 ms 177544 KB Output is correct
44 Correct 93 ms 183412 KB Output is correct
45 Correct 58 ms 185492 KB Output is correct
46 Correct 56 ms 187536 KB Output is correct
47 Correct 82 ms 193760 KB Output is correct
48 Incorrect 78 ms 200228 KB Output isn't correct
49 Halted 0 ms 0 KB -