Submission #590841

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
590841	2022-07-06T12:15:21 Z	yutabi	Horses (IOI15_horses)	C++14	Compilation error	0 ms	0 KB

horses

#include "horses.h"


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


#define MOD 1000000007


typedef long long ll;



struct node
{
	ll left_val=1;
	bool left_big=0;

	ll right_val=1;
	bool right_big=0;

	ll sell_price=0;
};



node seg_tree[2000007];


int n;

int* x;
int* y;


void merge(int node)
{
	ll res=seg_tree[node*2].right_val*seg_tree[node*2+1].left_val;

	if(res>=MOD || seg_tree[node*2].right_big || seg_tree[node*2+1].left_big || (ll)(seg_tree[node*2].sell_price)<=res*(ll)(seg_tree[node*2+1].sell_price))
	{
		seg_tree[node].right_val=seg_tree[node*2+1].right_val;
		seg_tree[node].right_big=seg_tree[node*2+1].right_big;
		seg_tree[node].sell_price=seg_tree[node*2+1].sell_price;
		
		seg_tree[node].left_big=0;

		if(res>=MOD)
		{
			seg_tree[node].left_big=1;
			res%=MOD;
		}

		res*=seg_tree[node*2].left_val;
		
		if(res>=MOD)
		{
			seg_tree[node].left_big=1;
			res%=MOD;
		}

		seg_tree[node].left_val=res;

		if(seg_tree[node*2].left_big || seg_tree[node*2].right_big || seg_tree[node*2+1].left_big)
		{
			seg_tree[node].left_big=1;
		}
	}

	else
	{
		seg_tree[node].left_val=seg_tree[node*2].left_val;
		seg_tree[node].left_big=seg_tree[node*2].left_big;
		seg_tree[node].sell_price=seg_tree[node*2].sell_price;
		
		seg_tree[node].right_big=0;

		if(res>=MOD)
		{
			seg_tree[node].right_big=1;
			res%=MOD;
		}

		res*=seg_tree[node*2+1].right_val;
		
		if(res>=MOD)
		{
			seg_tree[node].right_big=1;
			res%=MOD;
		}

		seg_tree[node].right_val=res;

		if(seg_tree[node*2+1].right_big || seg_tree[node*2].right_big || seg_tree[node*2+1].left_big)
		{
			seg_tree[node].right_big=1;
		}
	}
}


void build(int l=0, int r=n-1, int node=1)
{
	if(l==r)
	{
		seg_tree[node].left_val=x[l];
		seg_tree[node].left_big=0;
		
		seg_tree[node].right_val=1;
		seg_tree[node].right_big=0;

		seg_tree[node].sell_price=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[1].left_val*seg_tree[1].sell_price)%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[node].left_val=val;
		}

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

			seg_tree[node].sell_price=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

Compilation timeout while compiling horses