Submission #590860

#	Time	Username	Problem	Language	Result	Execution time	Memory
590860		yutabi	Horses (IOI15_horses)	C++14	100 / 100	133 ms	34252 KiB

horses

#include "horses.h"


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


#define MOD 1000000007


typedef long long ll;





ll seg_tree_left_val[2000007];
bool seg_tree_left_big[2000007];

ll seg_tree_right_val[2000007];
bool seg_tree_right_big[2000007];

ll seg_tree_sell_price[2000007];


int n;

int* x;
int* y;


void merge(int node)
{
	ll res=seg_tree_right_val[node*2]*seg_tree_left_val[node*2+1];

	if(res>=MOD || seg_tree_right_big[node*2] || seg_tree_left_big[node*2+1] || (ll)(seg_tree_sell_price[node*2])<=res*(ll)(seg_tree_sell_price[node*2+1]))
	{
		seg_tree_right_val[node]=seg_tree_right_val[node*2+1];
		seg_tree_right_big[node]=seg_tree_right_big[node*2+1];
		seg_tree_sell_price[node]=seg_tree_sell_price[node*2+1];
		
		seg_tree_left_big[node]=0;

		if(res>=MOD)
		{
			seg_tree_left_big[node]=1;
			res%=MOD;
		}

		res*=seg_tree_left_val[node*2];
		
		if(res>=MOD)
		{
			seg_tree_left_big[node]=1;
			res%=MOD;
		}

		seg_tree_left_val[node]=res;

		if(seg_tree_left_big[node*2] || seg_tree_right_big[node*2] || seg_tree_left_big[node*2+1])
		{
			seg_tree_left_big[node]=1;
		}
	}

	else
	{
		seg_tree_left_val[node]=seg_tree_left_val[node*2];
		seg_tree_left_big[node]=seg_tree_left_big[node*2];
		seg_tree_sell_price[node]=seg_tree_sell_price[node*2];
		
		seg_tree_right_big[node]=0;

		if(res>=MOD)
		{
			seg_tree_right_big[node]=1;
			res%=MOD;
		}

		res*=seg_tree_right_val[node*2+1];
		
		if(res>=MOD)
		{
			seg_tree_right_big[node]=1;
			res%=MOD;
		}

		seg_tree_right_val[node]=res;

		if(seg_tree_right_big[node*2+1] || seg_tree_right_big[node*2] || seg_tree_left_big[node*2+1])
		{
			seg_tree_right_big[node]=1;
		}
	}
}


void build(int l=0, int r=n-1, int node=1)
{
	if(l==r)
	{
		seg_tree_left_val[node]=x[l];
		seg_tree_left_big[node]=0;
		
		seg_tree_right_val[node]=1;
		seg_tree_right_big[node]=0;

		seg_tree_sell_price[node]=y[l];

		return;
	}

	int m=(l+r)/2;

	build(l,m,node*2);
	build(m+1,r,node*2+1);

	merge(node);
}

int query()
{
	return (seg_tree_left_val[1]*seg_tree_sell_price[1])%MOD;
}

void update(int h, int mode, int val, int l=0, int r=n-1, int node=1)
{
	if(l==r)
	{
		if(mode==1)
		{
			x[h]=val;

			seg_tree_left_val[node]=val;
		}

		if(mode==2)
		{
			y[h]=val;

			seg_tree_sell_price[node]=val;
		}

		return;
	}

	int m=(l+r)/2;

	if(h<=m)
	{
		update(h,mode,val,l,m,node*2);
	}

	else
	{
		update(h,mode,val,m+1,r,node*2+1);
	}

	merge(node);
}

int init(int N, int X[], int Y[])
{
	n=N;
	x=X;
	y=Y;

	build();

	return query();
}

int updateX(int pos, int val)
{
	update(pos,1,val);

	return query();
}

int updateY(int pos, int val)
{
	update(pos,2,val);

	return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:123:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |  return (seg_tree_left_val[1]*seg_tree_sell_price[1])%MOD;
      |                                                      ^

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