Submission #832439

#	Time	Username	Problem	Language	Result	Execution time	Memory
832439		happypotato	Horses (IOI15_horses)	C++17	17 / 100	1568 ms	43796 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int MOD = 1e9 + 7;
int bigmod(int b, int p) {
	b %= MOD;
	int res = 1;
	while (p) {
		if (p & 1) res = (res * b) % MOD;
		p >>= 1; b = (b * b) % MOD;
	}
	return res;
}
int modinv(int x) {
	return bigmod(x % MOD, MOD - 2);
}
const int mxN = 5e5 + 1;
int seg[(1 << 20)];
pii a[mxN];
int n;
void build(int l = 1, int r = n, int idx = 1) {
	if (l == r) {
		seg[idx] = a[l].ss;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, (idx << 1));
	build(mid + 1, r, (idx << 1) | 1);
	seg[idx] = max(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
void update(int pos, int val, int l = 1, int r = n, int idx = 1) {
	if (l == r) {
		seg[idx] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) update(pos, val, l, mid, (idx << 1));
	else update(pos, val, mid + 1, r, (idx << 1) | 1);
	seg[idx] = max(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
int query(int tl, int tr, int l = 1, int r = n, int idx = 1) {
	if (tl <= l && r <= tr) return seg[idx];
	int mid = (l + r) >> 1;
	int res = -1;
	if (tl <= mid) res = max(res, query(tl, tr, l, mid, (idx << 1)));
	if (tr > mid) res = max(res, query(tl, tr, mid + 1, r, (idx << 1) | 1));
	return res;
}
set<int> s;
int totmult = 1;

int findans() {
	if (s.empty()) return query(1, n);
	int multi = 1;
	int res = 0;
	set<int>::iterator it = s.end();
	while (res <= (int)(1e9) && it != s.begin()) {
		--it;
		res = (max(res, query(*it, n)) * a[*it].ff) % MOD;
		multi *= a[*it].ff;
	}
	res = (res * modinv(multi)) % MOD;
	res = (res * totmult) % MOD;
	return res;
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
	n = N;
	for (int i = 1; i <= n; i++) {
		a[i] = {X[i - 1], Y[i - 1]};
		if (a[i].ff >= 2) {
			s.insert(i);
			totmult = (totmult * a[i].ff) % MOD;
		}
	}
	build();
	return findans();
}

int32_t updateX(int32_t pos, int32_t val) {	
	pos++;
	if (a[pos].ff >= 2) {
		s.erase(s.find(pos));
		totmult = (totmult * modinv(a[pos].ff)) % MOD;
	}
	a[pos].ff = val;
	if (a[pos].ff >= 2) {
		s.insert(pos);
		totmult = (totmult * a[pos].ff) % MOD;
	}
	return findans();
}

int32_t updateY(int32_t pos, int32_t val) {
	pos++;
	a[pos].ss = val;
	update(pos, val);
	return findans();
}

#undef int

Compilation message (stderr)

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:81:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
   81 |  return findans();
      |         ~~~~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:95:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
   95 |  return findans();
      |         ~~~~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:102:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  102 |  return findans();
      |         ~~~~~~~^~

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