Submission #133588

#	Time	Username	Problem	Language	Result	Execution time	Memory
133588		MAMBA	Horses (IOI15_horses)	C++17	100 / 100	764 ms	42488 KiB

horses

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

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define lid id<<1
#define rid lid|1

typedef long long ll;
typedef pair<ll ,ll> pll;

const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 10;

int N;

ll A[MAXN], B[MAXN], segM[MAXN << 2], segX[MAXN << 2];
bool segH[MAXN << 2];

void build(int l = 0, int r = N, int id = 1) {
	if (l == r - 1) {
		segM[id] = A[l];
		segX[id] = B[l];
		segH[id] = segM[id] > 1;
		return;
	}
	int mid = l +r >> 1;
	build(l , mid , lid);
	build(mid , r ,rid);
	segM[id] = segM[lid] * segM[rid] % MOD;
	segX[id] = max(segX[lid] , segX[rid]);
	segH[id] = segH[lid] | segH[rid];
}

void segUpt(int pos , int l = 0 , int r = N, int id = 1) {
	if (l == r - 1) {
		segM[id] = A[l];
		segX[id] = B[l];
		segH[id] = segM[id] > 1;
		return;
	}
	int mid = l +r >> 1;
	if (pos < mid) segUpt(pos , l , mid , lid);
	else segUpt(pos , mid , r ,rid);
	segM[id] = segM[lid] * segM[rid] % MOD;
	segX[id] = max(segX[lid] , segX[rid]);
	segH[id] = segH[lid] | segH[rid];
}

int segRight(int lim , int l = 0, int r = N, int id = 1) {
	if (l >= lim || !segH[id]) return -1;
	if (l == r - 1) return l;
	int mid = l + r >> 1;
	int res = segRight(lim , mid , r, rid);
	if (!~res) res = segRight(lim , l , mid, lid);
	return res;
}

int segMax(int  lim , int l = 0, int r = N, int id = 1) {
	if (l >= lim) return segX[id];
	int mid = l +r >> 1;
	int res = segMax(lim , mid , r , rid);
	if (lim < mid) res = max(res , segMax(lim , l , mid , lid));
	return res;
}

int segMul(int lim , int l = 0, int r = N, int id = 1) {
	if (l >= lim) return 1;
	if (r <= lim) return segM[id];
	int mid = l + r >> 1;
	return 1ll * segMul(lim , l , mid , lid) * segMul(lim , mid , r, rid) % MOD;
}


int solve() {
	vector<pll> pos;
	ll mul = 1;
	int last = N;
	while (mul < 1e9 && last) {
		int id = segRight(last);
		if (!~id) {
			pos.pb({0 , segMax(0)});
			break;
		}
		mul *= A[id];
		last = id;
		pos.pb({id , segMax(id)});
	}
	ll best = 0;
	bool biger = false;
	for (auto e : pos) {
		ll local = e.second;
		if(biger) 
			local = best;
		else if (best > local) 
			local = best;
		local *= A[e.first];
		if (local >= MOD) {
			biger = true;
			local %= MOD;
		}
		best = local;
	}
	//cout <<  best * segMul(pos.back().first) % MOD << endl;
	return best * segMul(pos.back().first) % MOD;
}

int init(int N2, int X[], int Y[]) {
	N = N2;
	rep(i , 0 , N) {
		A[i] = X[i];
		B[i] = Y[i];
	}

	build();
	return solve();
}

int updateX(int pos, int val) {	
	A[pos] = val;
	segUpt(pos);
	return solve();
}

int updateY(int pos, int val) {
	B[pos] = val;
	segUpt(pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
horses.cpp: In function 'void segUpt(int, int, int, int)':
horses.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
horses.cpp: In function 'int segRight(int, int, int, int)':
horses.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
horses.cpp: In function 'int segMax(int, int, int, int)':
horses.cpp:62:30: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if (l >= lim) return segX[id];
                       ~~~~~~~^
horses.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
horses.cpp: In function 'int segMul(int, int, int, int)':
horses.cpp:71:30: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if (r <= lim) return segM[id];
                       ~~~~~~~^
horses.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
horses.cpp:73:72: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1ll * segMul(lim , l , mid , lid) * segMul(lim , mid , r, rid) % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:81:15: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
  while (mul < 1e9 && last) {
               ^~~
horses.cpp:107:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return best * segMul(pos.back().first) % MOD;
                       ~~~~~~~~~~~^~~~~
horses.cpp:107:41: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return best * segMul(pos.back().first) % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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