제출 #567867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567867		ngpin04	말 (IOI15_horses)	C++17	100 / 100	714 ms	58852 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 5e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct segtree {
	int n;
	vector <int> st;

	segtree(int _n = 0){
		n = _n;
		st.assign((n << 2) + 5, 0);
	}

	void update(int id, int l, int r, int pos, int val) {
		if (l > pos || r < pos)
			return;
		if (l == r) {
			st[id] = val;
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, pos, val);
		update(id << 1 | 1, mid + 1, r, pos, val);
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	}

	void update(int pos, int val) {
		update(1, 1, n, pos, val);
	}

	int getmax(int id, int l, int r, int u, int v) {
		if (l > v || r < u)
			return 0;
		if (l >= u && r <= v) 
			return st[id];
		int mid = (l + r) >> 1;
		int lnode = getmax(id << 1, l, mid, u, v);
		int rnode = getmax(id << 1 | 1, mid + 1, r, u, v);
		return max(lnode, rnode);
	}

	int getmax(int l, int r) {
		return getmax(1, 1, n, l, r);
	}
};

struct BIT {
	int n;
	vector <int> bit;

	BIT(int _n = 0){
		n = _n;
		bit.assign(n + 5, 1);
	}

	void update(int pos, int val) {
		for (; pos <= n; pos += pos & -pos)
			bit[pos] = (long long) bit[pos] * val % mod;
	}

	int getmul(int pos) {
		int res = 1;
		for (; pos; pos -= pos & -pos)
			res = (long long) res * bit[pos] % mod;
		return res;
	}
};


BIT bit;
segtree st; 

set <int> pos;

int l[N];
int r[N];
int x[N];
int y[N];
int n;

int bpow(int x, int k) {
	int res = 1;
	for (; k; k >>= 1, x = (long long) x * x % mod)
		if (k & 1) 
			res = (long long) res * x % mod;
	return res;
}

void build() {
	st = segtree(n);
	bit = BIT(n);
	pos.insert(0);
	pos.insert(n + 1);
	r[0] = n + 1;
	l[n + 1] = 0;

	for (int i = 1; i <= n; i++) if (x[i] > 1) {
		auto it = pos.upper_bound(i);
		int v = *it;
		int u = *(--it);
		l[i] = u;
		r[i] = v;

		r[u] = i;
		l[v] = i;
		
		pos.insert(i);
		bit.update(i, x[i]);
	}

	for (int i = 1; i <= n; i++)
		st.update(i, y[i]);
}

int solve() {
	vector <int> cand;
	long long tot = 1;
	for (int i = n + 1; i > 0 && tot < oo; i = l[i]) {
		cand.push_back(i);
		if (i <= n)
			tot *= x[i];
	}

	if (tot < oo && cand.back() != 1)
		cand.push_back(1);

	reverse(ALL(cand));

	pair <long long, long long> ans = mp(1, 0);

	long long cur = 1;
	int pos = 0;
	for (int it = 0; it + 1 < (int) cand.size(); it++) {
		int i = cand[it];
		int j = cand[it + 1];
		cur *= x[i];
		// cerr << cur << " " << i << " " << j << "\n";
		int mx = st.getmax(i, j - 1);

		if (cur / ans.fi > ans.se / mx) {
			pos = it;
			ans = mp(cur, mx);
		}

	}	

	int ret = bit.getmul(cand[pos]);
	ret = (long long) ret * st.getmax(cand[pos], cand[pos + 1] - 1) % mod;
	return ret;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 1; i <= n; i++)
		x[i] = X[i - 1];

	for (int i = 1; i <= n; i++)
		y[i] = Y[i - 1];

	build();
	return solve();
}

int updateX(int i, int val) {	
	i++;
	if (x[i] > 1) {
		pos.erase(i);
		auto it = pos.upper_bound(i);
		int v = *it;
		int u = *(--it);

		r[u] = v;
		l[v] = u;
	}

	bit.update(i, bpow(x[i], mod - 2));

	x[i] = val;

	bit.update(i, x[i]);

	if (x[i] > 1) {
		auto it = pos.upper_bound(i);
		int v = *it;
		int u = *(--it);

		r[u] = i;
		l[v] = i;

		r[i] = v;
		l[i] = u;

		pos.insert(i);
	}
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	st.update(pos, val);
	return solve();
}

//#include "grader.cpp"

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

horses.cpp: In function 'int rand(int, int)':
horses.cpp:20:11: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   20 |  return l + rd() % (r - l + 1);
      |         ~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In member function 'void BIT::update(int, int)':
horses.cpp:81:42: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   81 |    bit[pos] = (long long) bit[pos] * val % mod;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int BIT::getmul(int)':
horses.cpp:87:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |    res = (long long) res * bit[pos] % mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int bpow(int, int)':
horses.cpp:104:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  104 | int bpow(int x, int k) {
      |          ~~~~^
horses.cpp:100:5: note: shadowed declaration is here
  100 | int x[N];
      |     ^
horses.cpp:106:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |  for (; k; k >>= 1, x = (long long) x * x % mod)
      |                         ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:108:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  108 |    res = (long long) res * x % mod;
      |          ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:155:6: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  155 |  int pos = 0;
      |      ^~~
horses.cpp:96:11: note: shadowed declaration is here
   96 | set <int> pos;
      |           ^~~
horses.cpp:171:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  171 |  ret = (long long) ret * st.getmax(cand[pos], cand[pos + 1] - 1) % mod;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:175:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  175 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:22:11: note: shadowed declaration is here
   22 | const int N = 5e5 + 5;
      |           ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:221:17: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  221 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:96:11: note: shadowed declaration is here
   96 | set <int> pos;
      |           ^~~

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