Submission #137855

#	Time	Username	Problem	Language	Result	Execution time	Memory
137855		eohomegrownapps	Horses (IOI15_horses)	C++14	17 / 100	445 ms	119672 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll md = 1000000007;
vector<ll> x;
vector<ll> y;
ll n;
//overall maximum: prefix * maxy
struct Data{
	ll prefix=1; //prefix inclusive of max
	bool prefixgmd=false;
	ll suffix=1;
	bool suffixgmd=false;
	ll maxy=1;
};

Data combine(Data l, Data r){
	//first determine which has maximum
	Data ans;
	if (l.suffixgmd||r.prefixgmd){
		//r has maximum
		ans.prefix=(((l.prefix*l.suffix)%md)*r.prefix)%md;
		ans.prefixgmd=true;
		ans.suffix=r.suffix;
		ans.suffixgmd=r.suffixgmd;
		ans.maxy=r.maxy;
	} else {
		ll rval = l.suffix*r.prefix*r.maxy;
		ll lval = l.maxy;
		if (rval>lval){
			//r has maximum
			ans.maxy=r.maxy;
			if (l.prefixgmd){
				ans.prefixgmd=true;
				ans.prefix=(((l.prefix*l.suffix)%md)*r.prefix)%md;
			} else {
				ans.prefix=(l.prefix*l.suffix*r.prefix);
				if (ans.prefix>=md){
					ans.prefixgmd=true;
				} else {
					ans.prefixgmd=false;
				}
				ans.prefix%=md;
			}
			ans.suffix=r.suffix;
			ans.suffixgmd=r.suffixgmd;
		} else {
			//l has maximum
			ans.maxy=l.maxy;
			ans.prefixgmd=l.prefixgmd;
			ans.prefix=l.prefix;
			if (r.suffixgmd){
				ans.suffixgmd=true;
				ans.suffix=(((l.suffix*r.prefix)%md)*r.suffix)%md;
			} else {
				ans.suffix=(l.suffix*r.prefix*r.suffix);
				if (ans.suffix>=md){
					ans.suffixgmd=true;
				} else {
					ans.suffixgmd=false;
				}
				ans.suffix%=md;
			}
		}
	}
	return ans;
}

struct Node{
	ll s,e,m;
	Data d;
	Node *l, *r;
	Node(ll _s, ll _e){
		s=_s;e=_e;
		m=(s+e)/2;
		if (s==e){
			d.prefix=x[s];
			d.maxy=y[s];
			return;
		}
		l=new Node(s,m);
		r=new Node(m+1,e);
		d=combine(l->d,r->d);
	}

	void update(ll pos){
		if (s==e){
			d.prefix=x[pos];
			d.maxy=y[pos];
			d.suffix=1;
			d.prefixgmd=false;
			d.suffixgmd=false;
			return;
		}
		if (pos<=m){
			l->update(pos);
		} else {
			r->update(pos);
		}
		d=combine(l->d,r->d);
	}

	Data query(ll a, ll b){
		if (a==s&&b==e){
			return d;
		}
		if (b<=m){
			return l->query(a,b);
		} else if (m<a){
			return r->query(a,b);
		} else {
			return combine(l->query(a,m),r->query(m+1,b));
		}
	}
};
Node *root;
int init(int N, int X[], int Y[]) {
	n=N;
	x=vector<ll>(X,X+n);
	y=vector<ll>(Y,Y+n);
	root = new Node(0,n-1);
	Data d = root->query(0,n-1);
	return (d.prefix*d.maxy)%md;
}

int updateX(int pos, int val) {
	x[pos]=val;
	root->update(pos);
	Data d = root->query(0,n-1);
	return (d.prefix*d.maxy)%md;
}

int updateY(int pos, int val) {
	y[pos]=val;
	root->update(pos);
	Data d = root->query(0,n-1);
	return (d.prefix*d.maxy)%md;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:124:26: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (d.prefix*d.maxy)%md;
         ~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:131:26: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (d.prefix*d.maxy)%md;
         ~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:26: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (d.prefix*d.maxy)%md;
         ~~~~~~~~~~~~~~~~~^~~

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