oj.uz

Submission #789475

# Submission time Handle Problem Language Result Execution time Memory
789475 2023-07-21T12:32:10 Z Blagoj Horses (IOI15_horses) C++17
100 / 100
 481 ms 84428 KB 
#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

#define ll long long 

ll n, x[1500000], y[1500000], mod = 1e9 + 7;

struct SegmentTree {
	vector<ll> mul;
	vector<pair<ll, ll>> mx;

	void init() {
		mx.resize(n * 3, {0, 0});
		mul.resize(n * 3, 1);
	}

	void build(int k, int l, int r) {
		if (l == r) {
			mx[k] = { y[l], l };
			mul[k] = x[l];
			return;
		}
		build(k * 2, l, (l + r) / 2);
		build(k * 2 + 1, (l + r) / 2 + 1, r);
		mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
        mul[k] = (mul[k * 2] * mul[k * 2 + 1]) % mod;
    }

	void update(int k, int l, int r, int i, ll v, bool t) {
		if (l > i || r < i) return;
		if (l == r) {
			if (!t) mx[k].first = v;
			else mul[k] = v;
			return;
		}
		update(k * 2, l, (l + r) / 2, i, v, t);
		update(k * 2 + 1, (l + r) / 2 + 1, r, i, v, t);
		mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
		mul[k] = (mul[k * 2] * mul[k * 2 + 1]) % mod;
	}

	ll getX(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return 1;
		if (i <= l && r <= j) return mul[k];
		return (getX(k * 2, l, (l + r) / 2, i, j) * getX(k * 2 + 1, (l + r) / 2 + 1, r, i, j)) % mod;
	}

	pair<ll, ll> getY(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return {0, 0};
		if (i <= l && r <= j) return mx[k];
		return max( getY(k * 2, l, (l + r) / 2, i, j), getY(k * 2 + 1, (l + r) / 2 + 1, r, i, j) );
	}

} sgt;

set<int> s;

ll solve() {
	auto itf = --s.end(), its = --s.end();
	itf--;
	ll val = -1, id = n;
	for (int i = 0; i < 32 && its != s.begin(); i++) {
		pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
		if (t.first > val) {
			val = t.first;
			id = t.second;
		}
		val *= x[*itf];
		if (val > 2e9 || itf == s.begin()) break;
		its--;
		itf--;
	}
	return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % 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]; 
		if (x[i] != 1) s.insert(i);
	}
	s.insert(0);
	s.insert(n);
	sgt.init();
	sgt.build(1, 0, n - 1);
	return solve();
}

int updateX(int pos, int val) {	
	if (x[pos] != 1 && pos != 0) s.erase(pos);
	x[pos] = val;
	sgt.update(1, 0, n - 1, pos, val, 1);
	if (val != 1) s.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	sgt.update(1, 0, n -  1, pos, val, 0);
	return solve();
}

Compilation message

horses.cpp: In function 'long long int solve()':
horses.cpp:65:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |   pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
      |                                   ~~^~~
horses.cpp:71:7: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   71 |   if (val > 2e9 || itf == s.begin()) break;
      |       ^~~
horses.cpp:75:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
      |                              ~~^~~
horses.cpp:75:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
      |                                        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:11: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
   85 |  s.insert(n);
      |           ^
horses.cpp:87:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |  sgt.build(1, 0, n - 1);
      |                  ~~^~~
horses.cpp:88:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:94:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |  sgt.update(1, 0, n - 1, pos, val, 1);
      |                   ~~^~~
horses.cpp:96:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:101:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |  sgt.update(1, 0, n -  1, pos, val, 0);
      |                   ~~^~~~
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return solve();
      |         ~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 71676 KB Output is correct
2 Correct 303 ms 84428 KB Output is correct
3 Correct 291 ms 75520 KB Output is correct
4 Correct 326 ms 79372 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 224 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 316 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 444 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 1 ms 456 KB Output is correct
29 Correct 1 ms 320 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 2 ms 432 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 50 ms 51344 KB Output is correct
34 Correct 46 ms 51340 KB Output is correct
35 Correct 169 ms 81716 KB Output is correct
36 Correct 172 ms 81540 KB Output is correct
37 Correct 80 ms 49540 KB Output is correct
38 Correct 90 ms 62292 KB Output is correct
39 Correct 36 ms 49288 KB Output is correct
40 Correct 152 ms 76732 KB Output is correct
41 Correct 53 ms 49320 KB Output is correct
42 Correct 68 ms 49408 KB Output is correct
43 Correct 151 ms 77096 KB Output is correct
44 Correct 154 ms 77124 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 308 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 312 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 308 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 440 KB Output is correct
24 Correct 1 ms 432 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 448 KB Output is correct
27 Correct 3 ms 324 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 476 ms 75528 KB Output is correct
34 Correct 359 ms 84200 KB Output is correct
35 Correct 342 ms 75456 KB Output is correct
36 Correct 375 ms 79288 KB Output is correct
37 Correct 55 ms 51312 KB Output is correct
38 Correct 46 ms 51392 KB Output is correct
39 Correct 218 ms 81632 KB Output is correct
40 Correct 199 ms 81628 KB Output is correct
41 Correct 83 ms 49472 KB Output is correct
42 Correct 90 ms 62268 KB Output is correct
43 Correct 37 ms 49252 KB Output is correct
44 Correct 156 ms 76736 KB Output is correct
45 Correct 52 ms 49320 KB Output is correct
46 Correct 65 ms 49408 KB Output is correct
47 Correct 162 ms 77036 KB Output is correct
48 Correct 190 ms 77132 KB Output is correct
49 Correct 154 ms 54440 KB Output is correct
50 Correct 140 ms 54348 KB Output is correct
51 Correct 353 ms 83564 KB Output is correct
52 Correct 236 ms 83064 KB Output is correct
53 Correct 481 ms 52716 KB Output is correct
54 Correct 210 ms 66168 KB Output is correct
55 Correct 110 ms 50372 KB Output is correct
56 Correct 230 ms 78540 KB Output is correct
57 Correct 268 ms 51112 KB Output is correct
58 Correct 379 ms 51512 KB Output is correct
59 Correct 164 ms 77128 KB Output is correct