Submission #785191

#	Time	Username	Problem	Language	Result	Execution time	Memory
785191		fatemetmhr	Horses (IOI15_horses)	C++17	37 / 100	471 ms	38664 KiB

horses

//  ~ 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 = max(mx, ll(::mx[1]));
			return mx;
		}
		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 (stderr)

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:105:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |   rev[i] = pw(rat[i], mod - 2);
      |            ~~^~~~~~~~~~~~~~~~~
horses.cpp:112:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  115 | 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:117:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |  rev[pos] = pw(val, mod - 2);
      |             ~~^~~~~~~~~~~~~~
horses.cpp:124:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  127 | 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:130:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |  return get_ans();
      |         ~~~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23