oj.uz

Submission #785198

# Submission time Handle Problem Language Result Execution time Memory
785198 2023-07-17T07:05:04 Z fatemetmhr Horses (IOI15_horses) C++17
100 / 100
 501 ms 38716 KB 
//  ~ Be Name Khoda ~  //

#include "horses.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
set <int> av;
ll all = 1;

ll pw(ll a, ll b){
	ll ret = 1;
	for(; b; b >>= 1, a = a * a % mod)
		if(b & 1) ret = ret * a % mod;
	return ret;
}

void build(int l, int r, int v){
	if(r - l == 1){
		mx[v] = val[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v * 2);
	build(mid, r, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}

void update(int l, int r, int id, int val, int v){
	if(r - l == 1){
		mx[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(id < mid)
		update(l, mid, id, val, v * 2);
	else
		update(mid, r, id, val, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	return;
}

int get_max(int l, int r, int lq, int rq, int v){
	if(rq <= l || r <= lq)
		return 0;
	if(lq <= l && r <= rq)
		return mx[v];
	int mid = (l + r) >> 1;
	return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
}

ll get_ans(){
	//cout << av.size() << endl;
	if(av.empty())
		return mx[1];
	auto it = av.end(); it--;
	ll mx = 0;
	ll rem = all;
	//cout << "ha " << all << endl;
	while(true){
		int id = *it;
		ll have = get_max(0, n, id, n, 1);
		mx = max(mx, have);
		mx = mx * rat[id];
		rem = rem * rev[id] % mod;
		//cout << "we had " << mx << ' ' << rem << endl;
		if(it == av.begin()){
			assert(rem == 1);
			mx = max(mx, ll(::mx[1]));
			return mx % mod;
		}
		if(mx >= mod)
			break;
		it--;
	}

	return (mx % mod) * rem % mod;
}


int init(int N, int X[], int Y[]){
	n = N;
	for(int i = 0; i < n; i++){
		rat[i] = X[i];
		val[i] = Y[i];
		all = all * rat[i] % mod;
		rev[i] = pw(rat[i], mod - 2);
		if(rat[i] > 1)
			av.insert(i);
		//cout << i << ' ' << rat[i] << ' ' << av.size() << endl;

	}
	build(0, n, 1);
	return get_ans();
}

int updateX(int pos, int val){	
	all = all * rev[pos] % mod;
	rev[pos] = pw(val, mod - 2);
	all = all * val % mod;
	if(rat[pos] > 1)
		av.erase(pos);
	rat[pos] = val;
	if(val > 1)
		av.insert(pos);
	return get_ans();
}

int updateY(int pos, int val) {
	//cout << "here " << pos << ' ' << val << endl;
	update(0, n, pos, val, 1);
	return get_ans();
}

Compilation message

horses.cpp: In function 'void update(int, int, int, int, int)':
horses.cpp:48:39: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   48 | void update(int l, int r, int id, int val, int v){
      |                                   ~~~~^~~
horses.cpp:26:19: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |                   ^~~
horses.cpp: In function 'll get_ans()':
horses.cpp:76:5: warning: declaration of 'mx' shadows a global declaration [-Wshadow]
   76 |  ll mx = 0;
      |     ^~
horses.cpp:26:8: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:106:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  106 |   rev[i] = pw(rat[i], mod - 2);
      |            ~~^~~~~~~~~~~~~~~~~
horses.cpp:113:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:116:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  116 | int updateX(int pos, int val){
      |                      ~~~~^~~
horses.cpp:26:19: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |                   ^~~
horses.cpp:118:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  rev[pos] = pw(val, mod - 2);
      |             ~~^~~~~~~~~~~~~~
horses.cpp:125:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  125 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  128 | int updateY(int pos, int val) {
      |                      ~~~~^~~
horses.cpp:26:19: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |                   ^~~
horses.cpp:131:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  131 |  return get_ans();
      |         ~~~~~~~^~

Subtask #1
17.0 / 17.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 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 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 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 0 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 0 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 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 0 ms 212 KB Output is correct
14 Correct 0 ms 212 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 212 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 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 2 ms 380 KB Output is correct
28 Correct 1 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 2 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 38640 KB Output is correct
2 Correct 340 ms 38648 KB Output is correct
3 Correct 308 ms 38608 KB Output is correct
4 Correct 368 ms 38628 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 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 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 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 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 340 KB Output is correct
25 Correct 1 ms 412 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 1 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 2 ms 340 KB Output is correct
33 Correct 85 ms 14344 KB Output is correct
34 Correct 85 ms 14412 KB Output is correct
35 Correct 229 ms 37684 KB Output is correct
36 Correct 209 ms 37880 KB Output is correct
37 Correct 107 ms 14320 KB Output is correct
38 Correct 132 ms 26144 KB Output is correct
39 Correct 77 ms 14212 KB Output is correct
40 Correct 207 ms 37728 KB Output is correct
41 Correct 95 ms 14240 KB Output is correct
42 Correct 106 ms 14228 KB Output is correct
43 Correct 191 ms 37580 KB Output is correct
44 Correct 186 ms 37656 KB Output is correct

Subtask #5
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 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 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 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 280 KB Output is correct
17 Correct 0 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 0 ms 212 KB Output is correct
21 Correct 0 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 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 2 ms 340 KB Output is correct
28 Correct 1 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 2 ms 340 KB Output is correct
33 Correct 478 ms 38560 KB Output is correct
34 Correct 329 ms 38664 KB Output is correct
35 Correct 308 ms 38716 KB Output is correct
36 Correct 307 ms 38576 KB Output is correct
37 Correct 85 ms 14312 KB Output is correct
38 Correct 92 ms 14348 KB Output is correct
39 Correct 209 ms 37672 KB Output is correct
40 Correct 202 ms 37676 KB Output is correct
41 Correct 107 ms 14340 KB Output is correct
42 Correct 130 ms 26352 KB Output is correct
43 Correct 78 ms 14104 KB Output is correct
44 Correct 186 ms 37732 KB Output is correct
45 Correct 95 ms 14260 KB Output is correct
46 Correct 107 ms 14292 KB Output is correct
47 Correct 185 ms 37604 KB Output is correct
48 Correct 184 ms 37580 KB Output is correct
49 Correct 141 ms 16216 KB Output is correct
50 Correct 138 ms 16204 KB Output is correct
51 Correct 306 ms 38556 KB Output is correct
52 Correct 242 ms 38604 KB Output is correct
53 Correct 416 ms 16308 KB Output is correct
54 Correct 226 ms 29172 KB Output is correct
55 Correct 129 ms 14304 KB Output is correct
56 Correct 242 ms 38628 KB Output is correct
57 Correct 318 ms 15140 KB Output is correct
58 Correct 422 ms 15308 KB Output is correct
59 Correct 182 ms 37628 KB Output is correct