Submission #133584

#	Time	Username	Problem	Language	Result	Execution time	Memory
133584		Mahdi_Jfri	Horses (IOI15_horses)	C++14	17 / 100	1513 ms	51632 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] , n;

int x[maxn] , y[maxn];

set<int> st;

void updx(int p , int val , int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
	{
		mulx[v] = val;
		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;
}

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)
{
	if(x[p] > 1)
		st.erase(p);
	x[p] = val;
	updx(p , val);

	if(x[p] > 1)
		st.insert(p);
}

int solve()
{
	vector<int> tmp;
	for(auto it = st.end(); it != st.begin() && tmp.size() < 35;)
	{
		it--;
		tmp.pb(*it);
	}

	if(tmp.empty())
		return gety(0 , n);

	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;

		int mul = 1;
		for(int j = i + 1; j < m && good; j++)
		{
			mul = min((ll)2e9 , 1LL * mul * x[tmp[j]]);
			if(y[i] < 1LL * 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:32: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:99: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:102:14: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  vector<int> y;
              ^
horses.cpp:14:15: note: shadowed declaration is here
 int x[maxn] , y[maxn];
               ^
horses.cpp:113:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    mul = min((ll)2e9 , 1LL * mul * x[tmp[j]]);
          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:119: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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23