oj.uz

Submission #785188

# Submission time Handle Problem Language Result Execution time Memory
785188 2023-07-17T06:56:53 Z fatemetmhr Horses (IOI15_horses) C++17
37 / 100
 480 ms 38668 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() || 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:101:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  101 |   rev[i] = pw(rat[i], mod - 2);
      |            ~~^~~~~~~~~~~~~~~~~
horses.cpp:108:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  108 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:111:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  111 | 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:113:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |  rev[pos] = pw(val, mod - 2);
      |             ~~^~~~~~~~~~~~~~
horses.cpp:120:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:123:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  123 | 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:126:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  126 |  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 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 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 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

Subtask #2
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 0 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 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 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 2 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 38616 KB Output is correct
2 Correct 302 ms 38668 KB Output is correct
3 Correct 301 ms 38668 KB Output is correct
4 Correct 328 ms 38568 KB Output is correct

Subtask #4
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 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 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 1 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 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 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 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 2 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
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 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 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 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 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 Incorrect 2 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -