oj.uz

Submission #560966

# Submission time Handle Problem Language Result Execution time Memory
560966 2022-05-12T06:06:51 Z AriaH Horses (IOI15_horses) C++17
100 / 100
 555 ms 45144 KB 
#include "horses.h"
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 4e18;

int n, A[N], B[N];

struct node
{
	ll z, mx, my;
	void init(int a, int b)
	{
		z = a;
		mx = a;
		my = b;
	}
	friend node operator | (node a, node b)
	{
		node ret;
		ret.z = a.z * b.z % mod;
		ret.mx = max(a.mx, b.mx);
		ret.my = max(a.my, b.my);
		return ret;
	}
} seg[N << 2];

void build(int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl == tr)
	{
		seg[v].init(A[tl], B[tl]);
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] | seg[v << 1 | 1];
}

void Change(int p, int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl == tr)
	{
		seg[v].init(A[p], B[p]);
		return;
	}
	int mid = (tl + tr) >> 1;
	if(p <= mid) Change(p, v << 1, tl, mid);
	else Change(p, v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] | seg[v << 1 | 1];
}

pii get(int pos, int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl > pos) return Mp(-1, -1);
	if(seg[v].mx == 1) return Mp(tl, seg[v].my);
	if(tl == tr) return Mp(tl, B[tl]);
	int mid = (tl + tr) >> 1;
	pii cu = get(pos, v << 1 | 1, mid + 1, tr);
	if(A[cu.F] > 1)
	{
		return cu;
	}
	pii now = get(pos, v << 1, tl, mid);
	return Mp(now.F, max(now.S, cu.S));
}

ll ask(int l, int r, int v = 1, int tl = 0, int tr = n - 1)
{
	if(l > tr || r < tl || l > r) return 1;
	if(l <= tl && tr <= r) return seg[v].z;
	int mid = (tl + tr) >> 1;
	return ask(l, r, v << 1, tl, mid) * ask(l, r, v << 1 | 1, mid + 1, tr) % mod;
}

int solve()
{
	int id = n - 1;
	ll zarb = 1, best = 0;
	while(id >= 0)
	{
		pii now = get(id);
		zarb *= A[now.F];
		best = max(best, (ll)now.S);
		assert(id > now.F - 1);
		id = now.F - 1;
		assert(id >= -1);
		///printf("id = %d best = %lld zarb = %lld\n", id, best, zarb);
		if(zarb >= mod) break;
		best *= A[now.F];
		assert(best <= inf);
	}
	///printf("at the end best = %lld\n", best);
	best %= mod;
	if(id == -1)
	{
		return best;
	}
	///printf("now best = %lld id = %d ask = %lld\n", best, id, ask(0, id + 1));
	return best * ask(0, id + 1) % mod;
}

int init(int _N, int X[], int Y[])
{
	/*ll c = 1000000000;
	c = c * c % mod;
	cout << c << " " << c * c % mod << endl;*/
	n = _N;
	for(int i = 0; i < n; i ++) A[i] = X[i], B[i] = Y[i];
	build();
	return solve();
}

int updateX(int pos, int val)
{
	assert(val > 0);
	A[pos] = val;
	Change(pos);
	return solve();
}

int updateY(int pos, int val)
{
	assert(val > 0);
	B[pos] = val;
	Change(pos);
	return solve();
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:116:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |   return best;
      |          ^~~~
horses.cpp:119:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |  return best * ask(0, id + 1) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 304 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 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 212 KB Output is correct
21 Correct 0 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 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 2 ms 316 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 404 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 422 ms 33816 KB Output is correct
2 Correct 165 ms 45144 KB Output is correct
3 Correct 150 ms 37424 KB Output is correct
4 Correct 177 ms 41292 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 304 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 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 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 408 KB Output is correct
24 Correct 1 ms 320 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 316 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 368 KB Output is correct
32 Correct 3 ms 468 KB Output is correct
33 Correct 46 ms 36716 KB Output is correct
34 Correct 45 ms 36732 KB Output is correct
35 Correct 81 ms 43668 KB Output is correct
36 Correct 68 ms 43580 KB Output is correct
37 Correct 90 ms 34892 KB Output is correct
38 Correct 48 ms 35844 KB Output is correct
39 Correct 43 ms 34768 KB Output is correct
40 Correct 53 ms 38692 KB Output is correct
41 Correct 53 ms 34872 KB Output is correct
42 Correct 67 ms 35004 KB Output is correct
43 Correct 42 ms 39116 KB Output is correct
44 Correct 43 ms 39140 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 1 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 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 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 308 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 340 KB Output is correct
25 Correct 1 ms 312 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 320 KB Output is correct
33 Correct 413 ms 37636 KB Output is correct
34 Correct 166 ms 41644 KB Output is correct
35 Correct 158 ms 37432 KB Output is correct
36 Correct 179 ms 41268 KB Output is correct
37 Correct 46 ms 36740 KB Output is correct
38 Correct 46 ms 36812 KB Output is correct
39 Correct 86 ms 40652 KB Output is correct
40 Correct 73 ms 40692 KB Output is correct
41 Correct 83 ms 34876 KB Output is correct
42 Correct 46 ms 35808 KB Output is correct
43 Correct 33 ms 34892 KB Output is correct
44 Correct 49 ms 38692 KB Output is correct
45 Correct 53 ms 34824 KB Output is correct
46 Correct 65 ms 34880 KB Output is correct
47 Correct 42 ms 39124 KB Output is correct
48 Correct 45 ms 39116 KB Output is correct
49 Correct 146 ms 38800 KB Output is correct
50 Correct 138 ms 38712 KB Output is correct
51 Correct 184 ms 41468 KB Output is correct
52 Correct 127 ms 41632 KB Output is correct
53 Correct 555 ms 37128 KB Output is correct
54 Correct 191 ms 37580 KB Output is correct
55 Correct 116 ms 35936 KB Output is correct
56 Correct 118 ms 40584 KB Output is correct
57 Correct 298 ms 36604 KB Output is correct
58 Correct 432 ms 37048 KB Output is correct
59 Correct 50 ms 39068 KB Output is correct