Submission #133603

#	Time	Username	Problem	Language	Result	Execution time	Memory
133603		Mahdi_Jfri	Horses (IOI15_horses)	C++14	100 / 100	1385 ms	21496 KiB

horses

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;
const int mod = 1e9 + 7;

int maxy[maxn * 4] , mulx[maxn * 4] , t[maxn * 4] , n;

int x[maxn];

void updx(int p , int val , int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
	{
		mulx[v] = val;
		t[v] = val > 1;
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		updx(p , val , s , m , 2 * v);
	else
		updx(p , val , m , e , 2 * v + 1);

	mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod;
	t[v] = t[2 * v] + t[2 * v + 1];
}

void updy(int p , int val , int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
	{
		maxy[v] = val;
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		updy(p , val , s , m , 2 * v);
	else
		updy(p , val , m , e , 2 * v + 1);

	maxy[v] = max(maxy[2 * v] , maxy[2 * v + 1]);
}

int getx(int l , int r , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
		return mulx[v];
	else if(r <= s || e <= l)
		return 1;

	int m = (s + e) / 2;

	return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod;
}

int gety(int l , int r , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
		return maxy[v];
	if(r <= s || e <= l)
		return 0;

	int m = (s + e) / 2;
	return max(gety(l , r , s , m , 2 * v) , gety(l , r , m , e , 2 * v + 1));
}

void ux(int p , int val)
{
	x[p] = val;
	updx(p , val);
}

vector<int> tmp;

void get(int k = 35 , int s = 0 , int e = n , int v = 1)
{
	if(k <= 0 || !t[v])
		return;

	if(e - s < 2)
	{
		tmp.pb(s);
		return;
	}
	
	int m = (s + e) / 2;
	get(k , m , e , 2 * v + 1);
	k -= t[2 * v + 1];
	get(k , s , m , 2 * v);
}

int solve()
{
	tmp.clear();
	get();
	
  	tmp.pb(0);
	reverse(tmp.begin() , tmp.end());
	int m = tmp.size();
	tmp.pb(n);

	vector<int> y;
	for(int i = 0; i < m; i++)
		y.pb(gety(tmp[i] , tmp[i + 1]));

	for(int i = 0; i < m; i++)
	{
		bool good = 1;

		ll mul = 1;
		for(int j = i + 1; j < m && good; j++)
		{
			mul = min((ll)2e9 , 1LL * mul * x[tmp[j]]);
			if(y[i] <= mul * y[j])
				good = 0;
		}

		if(good)
			return 1LL * getx(0 , tmp[i] + 1) * y[i] % mod;
	}

	return -1;
}

int init(int N, int X[], int Y[])
{
	n = N;
	for(int i = 0; i < n; i++)
	{
		ux(i , X[i]);
		updy(i , Y[i]);
	}

	return solve();
}

int updateX(int pos, int val)
{
	ux(pos , val);
	return solve();
}

int updateY(int pos, int val)
{
	updy(pos , val);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void updx(int, int, int, int, int)':
horses.cpp:31:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getx(int, int, int, int, int)':
horses.cpp:61:77: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:107:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int m = tmp.size();
          ~~~~~~~~^~
horses.cpp:127:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    return 1LL * getx(0 , tmp[i] + 1) * y[i] % mod;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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