제출 #838550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838550		adrilen	말 (IOI15_horses)	C++17	100 / 100	671 ms	33228 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int maxn = 5e5, bit = 19;
constexpr ll mod = 1e9 + 7, siz = (1ll << bit);
using pii = pair<ll, bool>;

struct node {
	ll gfac; // Growth factor
	int best_pos;
	bool over_mod;
};

int n;
node segtree[siz * 2] = { 0 };
ll prices[siz] = { 0 };

void fm(ll &a)
{
	if (a >= mod) 
	{
		a %= mod;
	}
}


pair<ll, bool> query(int p, int l, int r, int gl, int gr)
{
	if (gl > gr) assert(0);

	if (l > gr || gl > r) return {1, false};
	// cout << l << " " << r << "\n";

	if (gl <= l && r <= gr) return {segtree[p].gfac, segtree[p].over_mod};

	int mid = (l + r) >> 1;
	pii le = query(p * 2, l, mid, gl, gr), ri = query(p * 2 + 1, mid + 1, r, gl, gr);

	le.first *= ri.first;
	le.second |= (ri.second || (le.first >= mod));
	fm(le.first);
	return le;
}


bool test_pos(int a, int b)
{
	int swapped = 0;
	if (a > b)
	{
		swap(a, b);
		swapped = 1;
	}


	pii le = {prices[a], false};
	pii re = query(1, 0, siz - 1, a + 1, b);

	re.first *= prices[b];
	re.second |= (re.first >= mod);

	// cout << a << " " << b << "\t" << le.first << " " << re.first << "\n";


	if (re.second) return 1 ^ swapped;
	if (re.first > le.first) return 1 ^ swapped;
	return 0 ^ swapped;
}


node comp(node a, const node &b)
{
	a.gfac *= b.gfac;
	a.over_mod |= (b.over_mod || (a.gfac >= mod));
	fm(a.gfac);

	return a;
}

void best_pos_comp(node &o, node &a, node &b)
{
	// cout << a.best_pos << " " << b.best_pos << "\n";
	if (test_pos(a.best_pos, b.best_pos))
	{
		o.best_pos = b.best_pos;
	} else {
		o.best_pos = a.best_pos;
	}
}

ll get_val_pos(int p)
{
	ll out = query(1, 0, siz - 1, 0, p).first * prices[p];
	fm(out);
	return out;
}

int init(int N, int X[], int Y[]) {
	n = N;

	for (int i = 0; i < n; i++)
	{
		prices[i] = Y[i];
		segtree[i + siz] = node{X[i], i, false};
	}

	for (int i = n; i < siz; i++)
	{
		segtree[i + siz] = node{1, i, false};
	}

	// for (int i = 1; i < siz * 2; i++)
	// {
	// 	if (__builtin_popcount(i) == 1) cout << "\n";

	// 	cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
	// }
	// cout << "\n";

	for (int i = siz - 1; i > 0; i--)
	{
		segtree[i] = comp(segtree[i * 2], segtree[i * 2 + 1]);
	}

	// for (int i = 1; i < siz * 2; i++)
	// {
	// 	if (__builtin_popcount(i) == 1) cout << "\n";

	// 	cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
	// }
	// cout << "\n";

	for (int i = siz - 1; i > 0; i--)
	{
		best_pos_comp(segtree[i], segtree[i * 2], segtree[i * 2 + 1]);

	}


	return (int)get_val_pos(segtree[1].best_pos);
}

void update_upwards(ll p)
{
	p += siz;
	while (p > 1)
	{
		p /= 2;
		segtree[p] = comp(segtree[p * 2], segtree[p * 2 + 1]);
		best_pos_comp(segtree[p], segtree[p * 2], segtree[p * 2 + 1]);
	}
}


int updateX(int pos, int val) {

	segtree[pos + siz].gfac = val;
	update_upwards(pos);

	return (int)get_val_pos(segtree[1].best_pos);
}

int updateY(int pos, int val) {
	prices[pos] = val;
	update_upwards(pos);

	return (int)get_val_pos(segtree[1].best_pos);
}

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

horses.cpp:17:29: warning: missing initializer for member 'node::best_pos' [-Wmissing-field-initializers]
   17 | node segtree[siz * 2] = { 0 };
      |                             ^
horses.cpp:17:29: warning: missing initializer for member 'node::over_mod' [-Wmissing-field-initializers]

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