제출 #416570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416570		ruadhan	말 (IOI15_horses)	C++17	0 / 100	67 ms	71908 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

set<int> xge2;
const int MOD = 1e9 + 7;
const int MX = 5e5 + 5;

struct ST
{
	int size;
	vector<ll> mul, mx;
	ST(int _size) : size(_size), mul(2 * size, 1), mx(2 * size) {}
	ll qmx(int l, int r)
	{
		ll ret = 0;
		for (l += size, r += size + 1; l < r; l /= 2, r /= 2)
		{
			if (l & 1)
				ret = max(ret, mul[l++]);
			if (r & 1)
				ret = max(ret, mul[--r]);
		}
		return ret;
	}
	ll qmul(int l, int r)
	{
		ll ret = 1;
		for (l += size, r += size + 1; l < r; l /= 2, r /= 2)
		{
			if (l & 1)
				ret = (ret * mul[l++]) % MOD;
			if (r & 1)
				ret = (ret * mul[--r]) % MOD;
		}
		return ret;
	}
	void umx(int i, ll v)
	{
		mx[i += size] = v;
		for (; i; i /= 2)
			mx[i] = max(mx[2 * i], mx[2 * i + 1]);
	}
	void umul(int i, ll v)
	{
		mul[i += size] = v;
		for (; i; i /= 2)
			mul[i] = (mul[2 * i] * mul[2 * i + 1]) % MOD;
	}
} st(2 * MX);

int n, x[MX], y[MX];

int ans()
{
	ll s = 1;
	int hi = n - 1;
	auto it = xge2.rbegin();
	vector<ll> a, b, c;
	while (it != xge2.rend())
	{
		int v = *it;
		a.push_back(v);
		b.push_back(s);
		c.push_back(st.qmx(v, hi));
		if (s > MOD)
			break;
		s *= x[v];
		hi = v - 1;
		it++;
	}
	pair<ll, int> mx_ans = {-1, -1};
	for (int i = 0; i < (int)a.size(); i++)
	{
		mx_ans = max(mx_ans, {s / b[i] * c[i], i});
	}
	return (st.qmul(0, a[mx_ans.second]) * c[mx_ans.second]) % MOD;
}

int init(int N, int X[], int Y[])
{
	n = N;
	for (int i = 0; i < N; ++i)
	{
		if (X[i] >= 2)
			xge2.insert(i);
		st.umul(i, X[i]);
		st.umx(i, Y[i]);
	}
	copy(X, X + N, x);
	copy(Y, Y + N, y);
	return ans();
}

int updateX(int pos, int val)
{
	if (val == 1 && xge2.find(pos) != xge2.end())
		xge2.erase(pos);
	else
		xge2.insert(pos);
	st.umul(pos, x[pos] = val);
	return ans();
}

int updateY(int pos, int val)
{
	st.umx(pos, y[pos] = val);
	return ans();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int ans()':
horses.cpp:78:37: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   78 |  return (st.qmul(0, a[mx_ans.second]) * c[mx_ans.second]) % MOD;
      |                                     ^
horses.cpp:78:59: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   78 |  return (st.qmul(0, a[mx_ans.second]) * c[mx_ans.second]) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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