oj.uz

Submission #784820

# Submission time Handle Problem Language Result Execution time Memory
784820 2023-07-16T14:56:28 Z zsombor Horses (IOI15_horses) C++17
100 / 100
 620 ms 85476 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "horses.h"
using namespace std;
using ll = long long;

struct node {
	int L, M, R;
	ll prod, mx;
};

int n;
ll MOD = 1e9 + 7;
vector <ll> x(5e5 + 1, 1);
vector <ll> y(5e5, 0);
vector <node> sgt(11e5);
vector <int> Lft(5e5 + 1, 0);
set <int> s;

void build_sgt(int a, int l, int r) {
	sgt[a].L = l;
	sgt[a].M = (l + r) / 2;
	sgt[a].R = r;
	if (r - l == 1) {
		sgt[a].prod = x[l];
		sgt[a].mx = y[l];
		return;
	}
	build_sgt(2 * a, l, sgt[a].M);
	build_sgt(2 * a + 1, sgt[a].M, r);
	sgt[a].prod = (sgt[2 * a].prod * sgt[2 * a + 1].prod) % MOD;
	sgt[a].mx = max(sgt[2 * a].mx, sgt[2 * a + 1].mx);
}

void update(int a, int i) {
	if (sgt[a].R - sgt[a].L == 1) {
		sgt[a].prod = x[i];
		sgt[a].mx = y[i];
		return;
	}
	if (i < sgt[a].M) update(2 * a, i);
	else update(2 * a + 1, i);
	sgt[a].prod = (sgt[2 * a].prod * sgt[2 * a + 1].prod) % MOD;
	sgt[a].mx = max(sgt[2 * a].mx, sgt[2 * a + 1].mx);
}

ll query_prod(int a, int l, int r) {
	if (r <= sgt[a].L || sgt[a].R <= l) return 1;
	if (l <= sgt[a].L && sgt[a].R <= r) return sgt[a].prod;
	return (query_prod(2 * a, l, r) * query_prod(2 * a + 1, l, r)) % MOD;
}

ll query_mx(int a, int l, int r) {
	if (r <= sgt[a].L || sgt[a].R <= l) return 1;
	if (l <= sgt[a].L && sgt[a].R <= r) return sgt[a].mx;
	return max(query_mx(2 * a, l, r), query_mx(2 * a + 1, l, r));
}

ll get_ans() {
	ll MX = 0, I = -1;
	for (int i = n; i > 0; i = Lft[i]) {
		MX *= x[i];
		if (MX > MOD) break;
		ll Y = query_mx(1, Lft[i], i);
		if (Y > MX) { MX = Y; I = i; }
	}
	return (query_prod(1, 0, Lft[I] + 1) * query_mx(1, Lft[I], I)) % MOD;
}

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]; }
	build_sgt(1, 0, n);
	for (int i = 1; i <= n; i++) {
		Lft[i] = x[i - 1] == 1 ? Lft[i - 1] : i - 1;
		if (x[i] > 1) s.insert(i);
	}
	s.insert(n);
	return get_ans();
}

int updateX(int pos, int val) {
	if (x[pos] == 1) {
		int r = *s.upper_bound(pos);
		Lft[pos] = Lft[r];
		Lft[r] = pos;
		s.insert(pos);
	}
	if (val == 1) {
		int r = *s.upper_bound(pos);
		Lft[r] = Lft[pos];
		s.erase(pos);
	}
	x[pos] = val;
	update(1, pos);
	return get_ans();
}

int updateY(int pos, int val) {
	y[pos] = val;
	update(1, pos);
	return get_ans();
}

Compilation message

horses.cpp: In function 'll get_ans()':
horses.cpp:69:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |  return (query_prod(1, 0, Lft[I] + 1) * query_mx(1, Lft[I], I)) % MOD;
      |                                                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:98:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:104:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |  return get_ans();
      |         ~~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44472 KB Output is correct
2 Correct 21 ms 44532 KB Output is correct
3 Correct 21 ms 44500 KB Output is correct
4 Correct 20 ms 44480 KB Output is correct
5 Correct 21 ms 44540 KB Output is correct
6 Correct 19 ms 44500 KB Output is correct
7 Correct 20 ms 44520 KB Output is correct
8 Correct 19 ms 44500 KB Output is correct
9 Correct 19 ms 44488 KB Output is correct
10 Correct 20 ms 44424 KB Output is correct
11 Correct 23 ms 44456 KB Output is correct
12 Correct 20 ms 44456 KB Output is correct
13 Correct 19 ms 44472 KB Output is correct
14 Correct 20 ms 44552 KB Output is correct
15 Correct 20 ms 44456 KB Output is correct
16 Correct 20 ms 44524 KB Output is correct
17 Correct 20 ms 44448 KB Output is correct
18 Correct 20 ms 44536 KB Output is correct
19 Correct 20 ms 44492 KB Output is correct
20 Correct 20 ms 44496 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 44512 KB Output is correct
2 Correct 19 ms 44448 KB Output is correct
3 Correct 19 ms 44500 KB Output is correct
4 Correct 20 ms 44448 KB Output is correct
5 Correct 20 ms 44548 KB Output is correct
6 Correct 20 ms 44512 KB Output is correct
7 Correct 19 ms 44432 KB Output is correct
8 Correct 19 ms 44496 KB Output is correct
9 Correct 21 ms 44424 KB Output is correct
10 Correct 24 ms 44544 KB Output is correct
11 Correct 21 ms 44464 KB Output is correct
12 Correct 20 ms 44436 KB Output is correct
13 Correct 20 ms 44456 KB Output is correct
14 Correct 20 ms 44424 KB Output is correct
15 Correct 20 ms 44428 KB Output is correct
16 Correct 21 ms 44528 KB Output is correct
17 Correct 20 ms 44500 KB Output is correct
18 Correct 24 ms 44460 KB Output is correct
19 Correct 20 ms 44416 KB Output is correct
20 Correct 23 ms 44460 KB Output is correct
21 Correct 20 ms 44528 KB Output is correct
22 Correct 20 ms 44508 KB Output is correct
23 Correct 20 ms 44500 KB Output is correct
24 Correct 20 ms 44500 KB Output is correct
25 Correct 21 ms 44632 KB Output is correct
26 Correct 22 ms 44632 KB Output is correct
27 Correct 22 ms 44532 KB Output is correct
28 Correct 21 ms 44580 KB Output is correct
29 Correct 20 ms 44500 KB Output is correct
30 Correct 21 ms 44620 KB Output is correct
31 Correct 25 ms 44500 KB Output is correct
32 Correct 22 ms 44440 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 76644 KB Output is correct
2 Correct 272 ms 85476 KB Output is correct
3 Correct 273 ms 76652 KB Output is correct
4 Correct 270 ms 80564 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44500 KB Output is correct
2 Correct 20 ms 44444 KB Output is correct
3 Correct 19 ms 44484 KB Output is correct
4 Correct 18 ms 44548 KB Output is correct
5 Correct 21 ms 44476 KB Output is correct
6 Correct 24 ms 44476 KB Output is correct
7 Correct 21 ms 44544 KB Output is correct
8 Correct 25 ms 44500 KB Output is correct
9 Correct 20 ms 44528 KB Output is correct
10 Correct 20 ms 44500 KB Output is correct
11 Correct 20 ms 44540 KB Output is correct
12 Correct 20 ms 44444 KB Output is correct
13 Correct 20 ms 44468 KB Output is correct
14 Correct 20 ms 44448 KB Output is correct
15 Correct 20 ms 44548 KB Output is correct
16 Correct 20 ms 44548 KB Output is correct
17 Correct 20 ms 44544 KB Output is correct
18 Correct 20 ms 44500 KB Output is correct
19 Correct 20 ms 44508 KB Output is correct
20 Correct 21 ms 44440 KB Output is correct
21 Correct 23 ms 44444 KB Output is correct
22 Correct 24 ms 44592 KB Output is correct
23 Correct 21 ms 44548 KB Output is correct
24 Correct 21 ms 44592 KB Output is correct
25 Correct 21 ms 44536 KB Output is correct
26 Correct 21 ms 44564 KB Output is correct
27 Correct 23 ms 44560 KB Output is correct
28 Correct 21 ms 44516 KB Output is correct
29 Correct 20 ms 44500 KB Output is correct
30 Correct 20 ms 44604 KB Output is correct
31 Correct 24 ms 44484 KB Output is correct
32 Correct 22 ms 44532 KB Output is correct
33 Correct 60 ms 52516 KB Output is correct
34 Correct 56 ms 52536 KB Output is correct
35 Correct 182 ms 82816 KB Output is correct
36 Correct 168 ms 82760 KB Output is correct
37 Correct 101 ms 50864 KB Output is correct
38 Correct 98 ms 63424 KB Output is correct
39 Correct 48 ms 50532 KB Output is correct
40 Correct 153 ms 77900 KB Output is correct
41 Correct 65 ms 50568 KB Output is correct
42 Correct 81 ms 50648 KB Output is correct
43 Correct 144 ms 78240 KB Output is correct
44 Correct 142 ms 78276 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 44484 KB Output is correct
2 Correct 19 ms 44500 KB Output is correct
3 Correct 20 ms 44540 KB Output is correct
4 Correct 20 ms 44480 KB Output is correct
5 Correct 21 ms 44500 KB Output is correct
6 Correct 19 ms 44432 KB Output is correct
7 Correct 22 ms 44424 KB Output is correct
8 Correct 20 ms 44500 KB Output is correct
9 Correct 20 ms 44508 KB Output is correct
10 Correct 22 ms 44496 KB Output is correct
11 Correct 19 ms 44492 KB Output is correct
12 Correct 20 ms 44476 KB Output is correct
13 Correct 19 ms 44500 KB Output is correct
14 Correct 19 ms 44540 KB Output is correct
15 Correct 20 ms 44500 KB Output is correct
16 Correct 19 ms 44496 KB Output is correct
17 Correct 19 ms 44500 KB Output is correct
18 Correct 20 ms 44472 KB Output is correct
19 Correct 20 ms 44628 KB Output is correct
20 Correct 19 ms 44524 KB Output is correct
21 Correct 21 ms 44536 KB Output is correct
22 Correct 19 ms 44452 KB Output is correct
23 Correct 20 ms 44484 KB Output is correct
24 Correct 24 ms 44580 KB Output is correct
25 Correct 20 ms 44608 KB Output is correct
26 Correct 19 ms 44500 KB Output is correct
27 Correct 22 ms 44524 KB Output is correct
28 Correct 20 ms 44500 KB Output is correct
29 Correct 22 ms 44592 KB Output is correct
30 Correct 20 ms 44628 KB Output is correct
31 Correct 21 ms 44556 KB Output is correct
32 Correct 21 ms 44548 KB Output is correct
33 Correct 507 ms 76620 KB Output is correct
34 Correct 272 ms 85456 KB Output is correct
35 Correct 276 ms 76664 KB Output is correct
36 Correct 252 ms 80616 KB Output is correct
37 Correct 58 ms 52492 KB Output is correct
38 Correct 57 ms 52568 KB Output is correct
39 Correct 177 ms 82792 KB Output is correct
40 Correct 164 ms 82824 KB Output is correct
41 Correct 96 ms 50632 KB Output is correct
42 Correct 103 ms 63416 KB Output is correct
43 Correct 50 ms 50496 KB Output is correct
44 Correct 159 ms 77984 KB Output is correct
45 Correct 65 ms 50576 KB Output is correct
46 Correct 75 ms 50536 KB Output is correct
47 Correct 161 ms 78284 KB Output is correct
48 Correct 144 ms 78268 KB Output is correct
49 Correct 198 ms 55508 KB Output is correct
50 Correct 171 ms 55576 KB Output is correct
51 Correct 334 ms 84756 KB Output is correct
52 Correct 240 ms 84240 KB Output is correct
53 Correct 620 ms 53940 KB Output is correct
54 Correct 268 ms 67496 KB Output is correct
55 Correct 157 ms 51500 KB Output is correct
56 Correct 256 ms 79692 KB Output is correct
57 Correct 326 ms 52168 KB Output is correct
58 Correct 437 ms 52824 KB Output is correct
59 Correct 151 ms 78272 KB Output is correct