oj.uz

Submission #379347

# Submission time Handle Problem Language Result Execution time Memory
379347 2021-03-18T02:31:05 Z pavement Horses (IOI15_horses) C++17
100 / 100
 1140 ms 162796 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;
const int MOD = 1e9 + 7;

int N, X[500005], Y[500005];

struct node {
	node *left, *right;
	int S, E;
	ld pv;
	pair<ld, int> val;
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val = make_pair(0., S);
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = max(left->val, right->val);
	}
	void prop() {
		if (S == E || pv == 0.) return;
		left->pv += pv;
		left->val.first += pv;
		right->pv += pv;
		right->val.first += pv;
		pv = 0.;
	}
	void upd(int l, int r, ld v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = max(left->val, right->val);
	}
} *root;

struct node2 {
	node2 *left, *right;
	int S, E, val, pv;
	node2(int _s, int _e) : S(_s), E(_e), val(1), pv(1) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node2(S, M);
		right = new node2(M + 1, E);
	}
	void prop() {
		if (S == E || pv == 1) return;
		left->pv = ((ll)left->pv * (ll)pv) % MOD;
		left->val = ((ll)left->val * (ll)pv) % MOD;
		right->pv = ((ll)right->pv * (ll)pv) % MOD;
		right->val = ((ll)right->val * (ll)pv) % MOD;
		pv = 1;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val = ((ll)val * (ll)v) % MOD;
			pv = ((ll)pv * (ll)v) % MOD;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
	}
	int qry(int p) {
		if (S == E) return val;
		prop();
		int M = (S + E) >> 1;
		if (p <= M) return left->qry(p);
		else return right->qry(p);
	}
} *root2;

ld f(int n) {
	return log(n) / 9.;
}

int init(int _N, int _X[], int _Y[]) {
	N = _N;
	for (int i = 1; i <= N; i++) X[i] = _X[i - 1];
	for (int i = 1; i <= N; i++) Y[i] = _Y[i - 1];
	root = new node(1, N);
	for (int i = 1; i <= N; i++)
		root->upd(i, N, f(X[i])), root->upd(i, i, f(Y[i]));
	root2 = new node2(1, N);
	for (int i = 1; i <= N; i++)
		root2->upd(i, N, X[i]), root2->upd(i, i, Y[i]);
	return root2->qry(root->val.second);
}

ll exp_mod(ll a, ll b) {
	a %= MOD;
	b %= (MOD - 1);
	ll r = 1ll;
	while (b) {
		if (b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b >>= 1ll;
	}
	assert(r <= INT_MAX);
	return r;
}

int updateX(int pos, int val) {
	pos++;
	root->upd(pos, N, -f(X[pos]));
	root2->upd(pos, N, exp_mod(X[pos], MOD - 2));
	X[pos] = val;
	root->upd(pos, N, f(X[pos]));
	root2->upd(pos, N, X[pos]);
	return root2->qry(root->val.second);
}

int updateY(int pos, int val) {
	pos++;
	root->upd(pos, pos, -f(Y[pos]));
	root2->upd(pos, pos, exp_mod(Y[pos], MOD - 2));
	Y[pos] = val;
	root->upd(pos, pos, f(Y[pos]));
	root2->upd(pos, pos, Y[pos]);
	return root2->qry(root->val.second);
}

Compilation message

horses.cpp: In member function 'void node2::prop()':
horses.cpp:59:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 |   left->pv = ((ll)left->pv * (ll)pv) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:60:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   60 |   left->val = ((ll)left->val * (ll)pv) % MOD;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:61:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   61 |   right->pv = ((ll)right->pv * (ll)pv) % MOD;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:62:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   62 |   right->val = ((ll)right->val * (ll)pv) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void node2::upd(int, int, int)':
horses.cpp:68:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |    val = ((ll)val * (ll)v) % MOD;
      |          ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:69:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |    pv = ((ll)pv * (ll)v) % MOD;
      |         ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:118:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  root2->upd(pos, N, exp_mod(X[pos], MOD - 2));
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  root2->upd(pos, pos, exp_mod(Y[pos], MOD - 2));
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 153964 KB Output is correct
2 Correct 1140 ms 162796 KB Output is correct
3 Correct 1139 ms 154092 KB Output is correct
4 Correct 1117 ms 157756 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 3 ms 620 KB Output is correct
24 Correct 4 ms 620 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 3 ms 748 KB Output is correct
27 Correct 3 ms 620 KB Output is correct
28 Correct 3 ms 620 KB Output is correct
29 Correct 2 ms 620 KB Output is correct
30 Correct 3 ms 620 KB Output is correct
31 Correct 3 ms 748 KB Output is correct
32 Correct 3 ms 748 KB Output is correct
33 Correct 726 ms 153068 KB Output is correct
34 Correct 704 ms 153112 KB Output is correct
35 Correct 710 ms 160236 KB Output is correct
36 Correct 712 ms 160080 KB Output is correct
37 Correct 656 ms 151276 KB Output is correct
38 Correct 689 ms 152300 KB Output is correct
39 Correct 631 ms 151196 KB Output is correct
40 Correct 684 ms 155032 KB Output is correct
41 Correct 629 ms 151276 KB Output is correct
42 Correct 624 ms 151276 KB Output is correct
43 Correct 661 ms 155720 KB Output is correct
44 Correct 671 ms 155500 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 3 ms 620 KB Output is correct
24 Correct 3 ms 620 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 3 ms 748 KB Output is correct
27 Correct 4 ms 620 KB Output is correct
28 Correct 3 ms 640 KB Output is correct
29 Correct 2 ms 620 KB Output is correct
30 Correct 3 ms 620 KB Output is correct
31 Correct 2 ms 620 KB Output is correct
32 Correct 2 ms 620 KB Output is correct
33 Correct 777 ms 153936 KB Output is correct
34 Correct 1140 ms 162796 KB Output is correct
35 Correct 1093 ms 153900 KB Output is correct
36 Correct 1119 ms 157932 KB Output is correct
37 Correct 733 ms 153200 KB Output is correct
38 Correct 704 ms 153068 KB Output is correct
39 Correct 715 ms 160108 KB Output is correct
40 Correct 714 ms 159980 KB Output is correct
41 Correct 652 ms 151276 KB Output is correct
42 Correct 692 ms 152300 KB Output is correct
43 Correct 634 ms 151148 KB Output is correct
44 Correct 697 ms 155116 KB Output is correct
45 Correct 634 ms 151168 KB Output is correct
46 Correct 633 ms 151276 KB Output is correct
47 Correct 668 ms 155500 KB Output is correct
48 Correct 660 ms 155500 KB Output is correct
49 Correct 1100 ms 155116 KB Output is correct
50 Correct 1087 ms 155244 KB Output is correct
51 Correct 822 ms 161928 KB Output is correct
52 Correct 848 ms 161644 KB Output is correct
53 Correct 1012 ms 153496 KB Output is correct
54 Correct 863 ms 154108 KB Output is correct
55 Correct 786 ms 152320 KB Output is correct
56 Correct 859 ms 157036 KB Output is correct
57 Correct 747 ms 152940 KB Output is correct
58 Correct 743 ms 153452 KB Output is correct
59 Correct 661 ms 155500 KB Output is correct