Submission #1088351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088351		Pacybwoah	Horses (IOI15_horses)	C++17	100 / 100	449 ms	57040 KiB

horses

#include "horses.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
typedef long long ll;
using namespace std;
namespace{
	int n;
	vector<int> seg;
	void build(int l, int r, int ind, vector<ll>& vec){
		if(l == r){
			seg[ind] = vec[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, ind * 2, vec);
		build(mid + 1, r, ind * 2 + 1, vec);
		seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
	}
	void modify(int l, int r, int num, int pos, int ind){
		if(l == r){
			seg[ind] = num;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) modify(l, mid, num, pos, ind * 2);
		else modify(mid + 1, r, num, pos, ind * 2 + 1);
		seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
	}
	int query(int l, int r, int start, int end, int ind){
		if(r < start || end < l) return 0;
		if(start <= l && r <= end) return seg[ind];
		int mid = (l + r) >> 1;
		return max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
	}
	const ll mod = 1e9 + 7;
	ll power(ll a, ll b){
		if(b == 1) return a % mod;
		if(b & 1) return power(a, b - 1) * a % mod;
		ll tmp = power(a, b / 2);
		return tmp * tmp % mod;
	}
	ll inverse(ll a){
		return power(a, mod - 2);
	}
	vector<ll> x, y;
	set<int> s;
	ll prod = 1;
}

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(n + 1);
	y.resize(n + 1);
	seg.resize(4 * n + 4);
	for(int i = 1; i <= n; i++) x[i] = X[i - 1], y[i] = Y[i - 1];
	build(1, n, 1, y);
	for(int i = 1; i <= n; i++) if(x[i] > 1) s.insert(i);
	for(int i = 1; i <= n; i++) prod = prod * x[i] % mod;
	if((int)s.size() == 0){
		return seg[1];
	}
	auto iter = prev(s.end());
	ll cur = 1;
	int curpos;
	vector<int> poss;
	while(1){
		curpos = (*iter);
		poss.push_back(curpos);
		cur *= x[curpos];
		if(cur > mod) break;
		if(iter == s.begin()){
			if(curpos != 1) poss.push_back(1);
			break;
		}
		iter = prev(iter);
	}
	reverse(poss.begin(), poss.end());
	__int128_t maxi = 1, now = 1;
	int sz = poss.size();
	for(int i = 0; i < sz; i++){
		now *= x[poss[i]];
		if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
		else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
	}
	return maxi % mod * inverse(now % mod) % mod * prod % mod;
}

int updateX(int pos, int val) {	
	pos++;
	if(x[pos] > 1) s.erase(pos);
	prod *= inverse(x[pos]);
	prod %= mod;
	x[pos] = val;
	prod *= val;
	prod %= mod;
	if(x[pos] > 1) s.insert(pos);
	if((int)s.size() == 0){
		return seg[1];
	}
	auto iter = prev(s.end());
	ll cur = 1;
	int curpos;
	vector<int> poss;
	while(1){
		curpos = (*iter);
		poss.push_back(curpos);
		cur *= x[curpos];
		if(cur > mod) break;
		if(iter == s.begin()){
			if(curpos != 1) poss.push_back(1);
			break;
		}
		iter = prev(iter);
	}
	reverse(poss.begin(), poss.end());
	__int128_t maxi = 1, now = 1;
	int sz = poss.size();
	for(int i = 0; i < sz; i++){
		now *= x[poss[i]];
		if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
		else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
	}
	return maxi % mod * inverse(now % mod) % mod * prod % mod;
}

int updateY(int pos, int val) {
	pos++;
	modify(1, n, val, pos, 1);
	y[pos] = val;
	if((int)s.size() == 0){
		return seg[1];
	}
	auto iter = prev(s.end());
	ll cur = 1;
	int curpos;
	vector<int> poss;
	while(1){
		curpos = (*iter);
		poss.push_back(curpos);
		cur *= x[curpos];
		if(cur > mod) break;
		if(iter == s.begin()){
			if(curpos != 1) poss.push_back(1);
			break;
		}
		iter = prev(iter);
	}
	reverse(poss.begin(), poss.end());
	__int128_t maxi = 1, now = 1;
	int sz = poss.size();
	for(int i = 0; i < sz; i++){
		now *= x[poss[i]];
		if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
		else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
	}
	return maxi % mod * inverse(now % mod) % mod * prod % mod;
}
// g++ -std=c++17 -Wall -Wextra -fsanitize=undefined -fsanitize=address -Wshadow -o run horses.cpp grader.cpp

Compilation message (stderr)

horses.cpp: In function 'void {anonymous}::build(int, int, int, std::vector<long long int>&)':
horses.cpp:14:20: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   14 |    seg[ind] = vec[l];
      |                    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   82 |  int sz = poss.size();
      |           ~~~~~~~~~^~
horses.cpp:88:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
   88 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |                              ~~~~^~~~~
horses.cpp:88:54: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
   88 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  120 |  int sz = poss.size();
      |           ~~~~~~~~~^~
horses.cpp:126:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  126 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |                              ~~~~^~~~~
horses.cpp:126:54: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  126 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:153:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  153 |  int sz = poss.size();
      |           ~~~~~~~~~^~
horses.cpp:159:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  159 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |                              ~~~~^~~~~
horses.cpp:159:54: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  159 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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