Submission #1018566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018566		AmirAli_H1	Horses (IOI15_horses)	C++17	100 / 100	1354 ms	50120 KiB

horses

// In the name of Allah

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node {
	ll mul, mx; int ind;
};

const int maxn = (1 << 19) + 4;
const int maxlg = 20;
const int mod = 1e9 + 7;

int n; pll A[maxn];
node t[2 * maxn], ca;

node f(node a, node b) {
	node res;
	res.mul = a.mul * b.mul % mod;
	res.mx = max(a.mx, b.mx);
	res.ind = max(a.ind, b.ind);
	return res;
}

void build(int v, int tl, int tr) {
	if (tr - tl == 1) {
		t[v].mul = A[tl].F; t[v].mx = A[tl].S;
		if (A[tl].F == 1) t[v].ind = -1;
		else t[v].ind = tl;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void upd(int v, int tl, int tr, int i) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v].mul = A[tl].F; t[v].mx = A[tl].S;
		if (A[tl].F == 1) t[v].ind = -1;
		else t[v].ind = tl;
		return ;
	}
	int mid = (tl + tr) / 2;
	upd(2 * v + 1, tl, mid, i); upd(2 * v + 2, mid, tr, i);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

node get_res(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ca;
	if (l == tl && r == tr) return t[v];
	int mid = (tl + tr) / 2;
	return f(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r));
}

ll get_ans() {
	ll mx = 1; int j = n;
	while (j > 0) {
		node res = get_res(0, 0, n, 0, j);
		int k = res.ind;
		if (k == -1) {
			mx = max(mx, res.mx); j = 0;
		}
		else {
			res = get_res(0, 0, n, k, j);
			mx = max(mx, res.mx) * A[k].F; j = k;
			if (mx >= mod) break;
		}
	}
	return (mx % mod) * get_res(0, 0, n, 0, j).mul % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) A[i] = Mp(X[i], Y[i]);
	ca.mul = 1; ca.mx = 0; ca.ind = -1;
	build(0, 0, n);
	return get_ans();
}

int updateX(int i, int val) {
	A[i].F = val;
	upd(0, 0, n, i);
	return get_ans();
}

int updateY(int i, int val) {
	A[i].S = val;
	upd(0, 0, n, i);
	return get_ans();
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:100:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:106:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  106 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:112:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  return get_ans();
      |         ~~~~~~~^~

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