제출 #108449

#제출 시각아이디문제언어결과실행 시간메모리
108449MetB말 (IOI15_horses)C++14
컴파일 에러
0 ms0 KiB
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>

typedef long long ll;

const ll MOD = 1e9 + 7, INF = 1e18;

using namespace std;

set < pair <int, ll> > s;

ll n, X[500000], m, Y[500000], ans;

ll qmult (ll a, ll b)
{
	ll s = 0;

	while (b)
	{
		if (b % 2) s = (s + a) % MOD;
		b /= 2;
		a = (a + a) % MOD;
	}

	return s;
}

struct SegTree
{
	ll t[2000000], start, type;
	void build (int n, int d)
	{
		start = 1;

		type = d;

		while (start < n) start <<= 1;

		for (int i = 0; i < n; i++)
			t[start + i] = (type ? Y[i] : X[i]);

		for (int i = start - 1; i; i--)
			t[i] = (type ? max (t[2 * i], t[2 * i + 1]) : t[2 * i] * t[2 * i + 1] % MOD);
	}

	void update (int x, ll d)
	{
		x += start;

		t[x] = d;

		x /= 2;

		while (x)
		{
			if (type) t[x] = max (t[2 * x], t[2 * x + 1]);
			else t[x] = t[2 * x] * t[2 * x + 1] % MOD;
			x /= 2;
		}
	}

	ll get (int l, int r)
	{
		ll sum = (type ? -INF : 1);

		l += start;
		r += start + 1;

		while (l < r)
		{
			if (l & 1) sum = (type ? max (sum, t[l++]) : sum * t[l++] % MOD);
			if (r & 1) sum = (type ? max (sum, t[--r]) : sum * t[--r] % MOD);

			l >>= 1;
			r >>= 1;
		}

		return sum;
	}

	ll& operator [] (const int& i)
	{
		return t[i + start];
	}
} t, tm;

ll find_answer (set < pair <int, ll> > :: iterator st)
{
	ans = 0;
	ll mul = 1;

	if (st -> first)
	{
		if (st == s.begin ())
		{
			ans = t.get (0, st -> first - 1);
		}
		else
		{
			auto k = st;
			k--;
			ans = t.get (k -> first, st -> first - 1);
		}
	}

	for (auto it = st; it != s.end (); it++)
	{
		mul *= it -> second;
		auto prev = it;
		it++;
		if (it == s.end ()) ans = max (ans, mul * t.get (prev -> first, n - 1));
		else ans = max (ans, mul * t.get (prev -> first, it -> first - 1));

		it = prev;
	}

	if (s.empty ()) return t.get (0, n - 1) % MOD;
	else 
	{
		auto k = st;
		if (k == s.begin ()) return ans % MOD;
		else 
		{
			k--;
			return qmult (ans, tm.get (0, k -> first)) % MOD;
		}
	}
}

set < pair <int, ll> > :: iterator new_start ()
{
	auto st = s.end ();
	if (!s.empty ())
	{
		st--;

		ll mul = 1;

		while (mul != INF)
		{
			if (mul >= 1000000000LL && st -> second >= 1000000000LL) mul = INF;
			else if ((mul * st -> second) > 1000000000LL) mul = INF;
			if (mul == INF) break;

			if (st == s.begin ()) break;

			mul *= st -> second;

			st--;
		}

		if (mul == INF) st++;
	}

	return st;
}

ll init (int n, vector <ll> a_X, vector <ll> a_Y)
{
	for (int i = 0; i < n; i++)
	{
		X[i] = a_X[i];
		if (X[i] != 1) s.insert (make_pair (i, X[i]));
	}

	for (int i = 0; i < n; i++)
		Y[i] = a_Y[i];

	t.build (n, 1);
	tm.build (n, 0);

	auto st = new_start ();

	return find_answer (st);
}

ll updateX (ll ind, ll v)
{
	if (X[ind] != 1)
		s.erase (make_pair (ind, X[ind]));

	if (v != 1)
		s.insert (make_pair (ind, v));

	X[ind] = v;

	tm.update (ind, v);

	st = new_start ();

	return find_answer (st);
}

ll updateY (ll ind, ll v)
{

	t.update (ind, v);

	return find_answer (st);
}

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

horses.cpp: In function 'll qmult(ll, ll)':
horses.cpp:27:5: warning: declaration of 's' shadows a global declaration [-Wshadow]
  ll s = 0;
     ^
horses.cpp:21:24: note: shadowed declaration is here
 set < pair <int, ll> > s;
                        ^
horses.cpp: In member function 'void SegTree::build(int, int)':
horses.cpp:43:2: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  {
  ^
horses.cpp:23:4: note: shadowed declaration is here
 ll n, X[500000], m, Y[500000], ans;
    ^
horses.cpp:53:22: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   for (int i = start - 1; i; i--)
                ~~~~~~^~~
horses.cpp: In member function 'void SegTree::update(int, ll)':
horses.cpp:59:5: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   x += start;
   ~~^~~~~~~~
horses.cpp: In member function 'll SegTree::get(int, int)':
horses.cpp:77:5: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   l += start;
   ~~^~~~~~~~
horses.cpp:78:5: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   r += start + 1;
   ~~^~~~~~~~~~~~
horses.cpp: In function 'll find_answer(std::set<std::pair<int, long long int> >::iterator)':
horses.cpp:122:69: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if (it == s.end ()) ans = max (ans, mul * t.get (prev -> first, n - 1));
                                                                   ~~^~~
horses.cpp:128:37: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if (s.empty ()) return t.get (0, n - 1) % MOD;
                                   ~~^~~
horses.cpp: In function 'll init(int, std::vector<long long int>, std::vector<long long int>)':
horses.cpp:169:49: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll init (int n, vector <ll> a_X, vector <ll> a_Y)
                                                 ^
horses.cpp:23:4: note: shadowed declaration is here
 ll n, X[500000], m, Y[500000], ans;
    ^
horses.cpp: In function 'll updateX(ll, ll)':
horses.cpp:198:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  tm.update (ind, v);
                   ^
horses.cpp:200:2: error: 'st' was not declared in this scope
  st = new_start ();
  ^~
horses.cpp:200:2: note: suggested alternative: 't'
  st = new_start ();
  ^~
  t
horses.cpp: In function 'll updateY(ll, ll)':
horses.cpp:208:18: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  t.update (ind, v);
                  ^
horses.cpp:210:22: error: 'st' was not declared in this scope
  return find_answer (st);
                      ^~
horses.cpp:210:22: note: suggested alternative: 't'
  return find_answer (st);
                      ^~
                      t