oj.uz

Submission #302246

# Submission time Handle Problem Language Result Execution time Memory
302246 2020-09-18T14:44:54 Z square1001 Horses (IOI15_horses) C++14
100 / 100
 690 ms 53496 KB 
#include "horses.h"
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
class segment_tree_1 {
private:
	int sz;
	vector<int> val;
	int range_mul(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return 1;
		if(a <= l && r <= b) return val[k];
		int lc = range_mul(a, b, k * 2, l, (l + r) >> 1);
		int rc = range_mul(a, b, k * 2 + 1, (l + r) >> 1, r);
		return int(1LL * lc * rc % mod);
	}
public:
	segment_tree_1() : sz(0), val() {};
	segment_tree_1(int N) {
		sz = 1;
		while(sz < N) sz *= 2;
		val = vector<int>(sz * 2, 1);
	}
	void update(int pos, int x) {
		pos += sz;
		val[pos] = x;
		while(pos > 1) {
			pos >>= 1;
			val[pos] = int(1LL * val[pos * 2] * val[pos * 2 + 1] % mod);
		}
	}
	int range_mul(int l, int r) {
		return range_mul(l, r, 1, 0, sz);
	}
};
class segment_tree_2 {
private:
	int sz;
	vector<int> val;
	int range_max(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return 1;
		if(a <= l && r <= b) return val[k];
		int lc = range_max(a, b, k * 2, l, (l + r) >> 1);
		int rc = range_max(a, b, k * 2 + 1, (l + r) >> 1, r);
		return max(lc, rc);
	}
public:
	segment_tree_2() : sz(0), val() {};
	segment_tree_2(int N) {
		sz = 1;
		while(sz < N) sz *= 2;
		val = vector<int>(sz * 2, 0);
	}
	void update(int pos, int x) {
		pos += sz;
		val[pos] = x;
		while(pos > 1) {
			pos >>= 1;
			val[pos] = max(val[pos * 2], val[pos * 2 + 1]);
		}
	}
	int range_max(int l, int r) {
		return range_max(l, r, 1, 0, sz);
	}
};
int N; set<int> s; vector<int> X, Y;
segment_tree_1 seg1;
segment_tree_2 seg2;
int solve() {
	long long mult = 1;
	set<int>::iterator it = s.end();
	vector<int> st = { N };
	while(it != s.begin()) {
		--it;
		mult *= X[*it];
		st.push_back(*it);
		if(mult > 1000000000) break;
	}
	if(mult <= 1000000000 && st.back() != 0) {
		st.push_back(0);
	}
	reverse(st.begin(), st.end());
	int ini = st[0];
	int coeff = seg1.range_mul(0, ini + 1);
	long long ans = 0;
	mult = 1;
	for(int i = 0; i < int(st.size()) - 1; ++i) {
		int mx = seg2.range_max(st[i], st[i + 1]);
		ans = max(ans, mult * mx);
		if(i != int(st.size()) - 2) {
			mult *= X[st[i + 1]];
		}
	}
	ans = (ans % mod) * coeff % mod;
	return int(ans);
}
int init(int N_, int X_[], int Y_[]) {
	N = N_;
	X = vector<int>(X_, X_ + N);
	Y = vector<int>(Y_, Y_ + N);
	seg1 = segment_tree_1(N);
	seg2 = segment_tree_2(N);
	for(int i = 0; i < N; ++i) {
		if(X[i] >= 2) {
			s.insert(i);
		}
		seg1.update(i, X[i]);
		seg2.update(i, Y[i]);
	}
	return solve();
}
int updateX(int pos, int val) {
	if(X[pos] == 1 && val >= 2) {
		s.insert(pos);
	}
	if(X[pos] >= 2 && val == 1) {
		s.erase(pos);
	}
	X[pos] = val;
	seg1.update(pos, val);
	return solve();
}
int updateY(int pos, int val) {
	Y[pos] = val;
	seg2.update(pos, val);
	return solve();
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 40880 KB Output is correct
2 Correct 378 ms 53496 KB Output is correct
3 Correct 386 ms 44664 KB Output is correct
4 Correct 425 ms 48504 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 138 ms 16632 KB Output is correct
34 Correct 138 ms 20472 KB Output is correct
35 Correct 294 ms 50808 KB Output is correct
36 Correct 286 ms 50808 KB Output is correct
37 Correct 175 ms 18680 KB Output is correct
38 Correct 201 ms 31480 KB Output is correct
39 Correct 130 ms 18432 KB Output is correct
40 Correct 274 ms 45944 KB Output is correct
41 Correct 148 ms 18552 KB Output is correct
42 Correct 161 ms 18684 KB Output is correct
43 Correct 261 ms 46328 KB Output is correct
44 Correct 265 ms 46272 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 690 ms 42520 KB Output is correct
34 Correct 380 ms 53372 KB Output is correct
35 Correct 386 ms 44664 KB Output is correct
36 Correct 419 ms 48636 KB Output is correct
37 Correct 138 ms 20472 KB Output is correct
38 Correct 136 ms 20472 KB Output is correct
39 Correct 298 ms 50808 KB Output is correct
40 Correct 286 ms 50808 KB Output is correct
41 Correct 178 ms 18808 KB Output is correct
42 Correct 210 ms 31424 KB Output is correct
43 Correct 132 ms 18432 KB Output is correct
44 Correct 265 ms 45956 KB Output is correct
45 Correct 156 ms 18552 KB Output is correct
46 Correct 162 ms 18552 KB Output is correct
47 Correct 258 ms 46200 KB Output is correct
48 Correct 262 ms 46304 KB Output is correct
49 Correct 265 ms 23544 KB Output is correct
50 Correct 245 ms 23672 KB Output is correct
51 Correct 425 ms 52728 KB Output is correct
52 Correct 371 ms 52216 KB Output is correct
53 Correct 678 ms 21880 KB Output is correct
54 Correct 399 ms 35320 KB Output is correct
55 Correct 232 ms 19576 KB Output is correct
56 Correct 385 ms 47704 KB Output is correct
57 Correct 462 ms 20216 KB Output is correct
58 Correct 536 ms 20768 KB Output is correct
59 Correct 256 ms 46200 KB Output is correct