Submission #641122

#	Time	Username	Problem	Language	Result	Execution time	Memory
641122		ymm	Horses (IOI15_horses)	C++17	100 / 100	756 ms	45352 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 1<<19;
static const int mod = 1e9+7;
static int n;

int seg[N<<1];

static int get(int l, int r, int i=0, int b=0, int e=n)
{
	if (l <= b && e <= r)
		return seg[i];
	if (r <= b || e <= l)
		return 0;
	return max(get(l,r,2*i+1,b,(b+e)/2),get(l,r,2*i+2,(b+e)/2,e));
}

static void sset(int p, int x, int i=0, int b=0, int e=n)
{
	if (e-b == 1) {
		seg[i] = x;
		return;
	}
	if (p < (b+e)/2)
		sset(p,x,2*i+1,b,(b+e)/2);
	else
		sset(p,x,2*i+2,(b+e)/2,e);
	seg[i] = max(seg[2*i+1], seg[2*i+2]);
}

int *X, *Y;
set<int> nonone;
ll proall;

static ll mpow(ll x, ll y){ll ans=1;while(y){ans=y&1?ans*x%mod:ans;x=x*x%mod;y>>=1;}return ans;}

static int calc()
{
	ll ansn = 0, ansd = 1;
	ll suf = 1;
	auto it = --nonone.end();
	while (it != nonone.begin() && suf < INT_MAX) {
		int r = *(it--);
		int l = *it;
		ll mx = get(l, r);
		// if (mx / suf > ansn / ansd)
		if (mx * ansd > ansn * suf) {
			ansn = mx;
			ansd = suf;
		}
		suf *= X[l];
	}
	ansn %= mod;
	ansd %= mod;
	return proall * ansn % mod * mpow(ansd, mod-2) % mod;
}

int init(int n, int X[], int Y[]) {
	::X = X; ::Y = Y; ::n = n;
	proall = 1;
	Loop (i,0,n) {
		proall = proall * X[i] % mod;
		sset(i, Y[i]);
		if (i==0 || X[i] != 1)
			nonone.insert(i);
	}
	nonone.insert(n);
	return calc();
}

int updateX(int pos, int val) {	
	if (pos==0 || X[pos] != 1) nonone.erase(pos);
	proall = proall * mpow(X[pos], mod-2) % mod;
	X[pos] = val;
	if (pos==0 || X[pos] != 1) nonone.insert(pos);
	proall = proall * X[pos] % mod;
	return calc();
}

int updateY(int pos, int val) {
	Y[pos] = val;
	sset(pos, val);
	return calc();
}

Compilation message (stderr)

horses.cpp: In function 'int calc()':
horses.cpp:62:49: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   62 |  return proall * ansn % mod * mpow(ansd, mod-2) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:65:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   65 | int init(int n, int X[], int Y[]) {
      |                          ~~~~^~~
horses.cpp:38:10: note: shadowed declaration is here
   38 | int *X, *Y;
      |          ^
horses.cpp:65:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   65 | int init(int n, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:38:6: note: shadowed declaration is here
   38 | int *X, *Y;
      |      ^
horses.cpp:65:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   65 | int init(int n, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:12:12: note: shadowed declaration is here
   12 | static int n;
      |            ^
horses.cpp:70:8: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   70 |   sset(i, Y[i]);
      |        ^
horses.cpp:72:18: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
   72 |    nonone.insert(i);
      |                  ^

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