Submission #789475

#	Time	Username	Problem	Language	Result	Execution time	Memory
789475		Blagoj	Horses (IOI15_horses)	C++17	100 / 100	481 ms	84428 KiB

horses

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

using namespace std;

#define ll long long 

ll n, x[1500000], y[1500000], mod = 1e9 + 7;

struct SegmentTree {
	vector<ll> mul;
	vector<pair<ll, ll>> mx;

	void init() {
		mx.resize(n * 3, {0, 0});
		mul.resize(n * 3, 1);
	}

	void build(int k, int l, int r) {
		if (l == r) {
			mx[k] = { y[l], l };
			mul[k] = x[l];
			return;
		}
		build(k * 2, l, (l + r) / 2);
		build(k * 2 + 1, (l + r) / 2 + 1, r);
		mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
        mul[k] = (mul[k * 2] * mul[k * 2 + 1]) % mod;
    }

	void update(int k, int l, int r, int i, ll v, bool t) {
		if (l > i || r < i) return;
		if (l == r) {
			if (!t) mx[k].first = v;
			else mul[k] = v;
			return;
		}
		update(k * 2, l, (l + r) / 2, i, v, t);
		update(k * 2 + 1, (l + r) / 2 + 1, r, i, v, t);
		mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
		mul[k] = (mul[k * 2] * mul[k * 2 + 1]) % mod;
	}

	ll getX(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return 1;
		if (i <= l && r <= j) return mul[k];
		return (getX(k * 2, l, (l + r) / 2, i, j) * getX(k * 2 + 1, (l + r) / 2 + 1, r, i, j)) % mod;
	}

	pair<ll, ll> getY(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return {0, 0};
		if (i <= l && r <= j) return mx[k];
		return max( getY(k * 2, l, (l + r) / 2, i, j), getY(k * 2 + 1, (l + r) / 2 + 1, r, i, j) );
	}

} sgt;

set<int> s;

ll solve() {
	auto itf = --s.end(), its = --s.end();
	itf--;
	ll val = -1, id = n;
	for (int i = 0; i < 32 && its != s.begin(); i++) {
		pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
		if (t.first > val) {
			val = t.first;
			id = t.second;
		}
		val *= x[*itf];
		if (val > 2e9 || itf == s.begin()) break;
		its--;
		itf--;
	}
	return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < N; i++) { 
		x[i] = X[i], y[i] = Y[i]; 
		if (x[i] != 1) s.insert(i);
	}
	s.insert(0);
	s.insert(n);
	sgt.init();
	sgt.build(1, 0, n - 1);
	return solve();
}

int updateX(int pos, int val) {	
	if (x[pos] != 1 && pos != 0) s.erase(pos);
	x[pos] = val;
	sgt.update(1, 0, n - 1, pos, val, 1);
	if (val != 1) s.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	sgt.update(1, 0, n -  1, pos, val, 0);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'long long int solve()':
horses.cpp:65:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |   pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
      |                                   ~~^~~
horses.cpp:71:7: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   71 |   if (val > 2e9 || itf == s.begin()) break;
      |       ^~~
horses.cpp:75:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
      |                              ~~^~~
horses.cpp:75:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |  return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
      |                                        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:11: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
   85 |  s.insert(n);
      |           ^
horses.cpp:87:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |  sgt.build(1, 0, n - 1);
      |                  ~~^~~
horses.cpp:88:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:94:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |  sgt.update(1, 0, n - 1, pos, val, 1);
      |                   ~~^~~
horses.cpp:96:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:101:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |  sgt.update(1, 0, n -  1, pos, val, 0);
      |                   ~~^~~~
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return solve();
      |         ~~~~~^~

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