Submission #43594

#	Time	Username	Problem	Language	Result	Execution time	Memory
43594		gnoor	Horses (IOI15_horses)	C++14	100 / 100	309 ms	146536 KiB

horses

#include "horses.h"
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

const int mod = 1000000007;

struct number {
	long long val;
	bool overflow;
	number() {
		val=0;
		overflow=false;
	}
	number(long long _val) {
		val=_val;
		overflow=false;
	}

	number(long long _val,bool _of) {
		val=_val;
		overflow=_of;
	}
	bool operator< (const number &r) const {
		if (overflow||r.overflow) {
			return r.overflow;
		}
		return val<r.val;
	}

	number operator+(const number &r) const {
		return number((val+r.val)%mod,(val+r.val)>=mod||overflow||r.overflow);
	}
	number operator-(const number &r) const {
		return number(((val-r.val)%mod+mod)%mod,(val-r.val)<0||overflow||r.overflow);
	}
	number operator*(const number &r) const {
		return number((val*r.val)%mod,(val*r.val)>=mod||overflow||r.overflow);
	}
	number& operator=(const long long _val) {
		val=_val%mod;
		overflow=_val>=mod;
		return *this;
	}
};

struct node {
	number xval;
	number ymax;
	number pre;
	number suf;	
	void combine(const node &l,const node &r) {
		xval=l.xval*r.xval;
		if (l.ymax<l.suf*r.pre*r.ymax) {
			//choose right
			ymax=r.ymax;
			pre=l.xval*r.pre;
			suf=r.suf;
		} else {
			//choose left
			ymax=l.ymax;
			pre=l.pre;
			suf=l.suf*r.xval;	
		}
	}
};

node seg[2000100];
number x[500100];
number y[500100];
int n;

void build(int idx,int l,int r) {
	if (l+1==r) {
		seg[idx].xval=x[l];
		seg[idx].pre=x[l];
		seg[idx].suf=1;
		seg[idx].ymax=y[l];
		return;
	}					
	int m=(l+r)>>1;
	build(idx*2+1,l,m);
	build(idx*2+2,m,r);
	seg[idx].combine(seg[idx*2+1],seg[idx*2+2]);
}

void update(int idx,int l,int r,int k) {
	if (k<l||k>=r) return;
	if (l+1==r) {
		seg[idx].xval=x[l];
		seg[idx].pre=x[l];
		seg[idx].suf=1;
		seg[idx].ymax=y[l];
		return;
	}
	int m=(l+r)>>1;
	update(idx*2+1,l,m,k);
	update(idx*2+2,m,r,k);
	seg[idx].combine(seg[idx*2+1],seg[idx*2+2]);
}

//void print(int idx,int l,int r) {
	//printf("%d %d: %lld %lld %lld %lld\n",l,r,seg[idx].xval.val,seg[idx].ymax.val,seg[idx].suf.val,seg[idx].pre.val);
	//if (l+1==r) return;
	//int m=(l+r)>>1;
	//print(idx*2+1,l,m);
	//print(idx*2+2,m,r);
//}

int init(int N, int X[], int Y[]) {
	n=N;
	for (int i=0;i<n;i++) {
		x[i]=X[i];
		y[i]=Y[i];
	}
	build(0,0,n);
	//print(0,0,n);
	return (seg[0].pre*seg[0].ymax).val;
}

int updateX(int pos, int val) {	
	x[pos]=val;
	update(0,0,n,pos);
	return (seg[0].pre*seg[0].ymax).val;
}

int updateY(int pos, int val) {
	y[pos]=val;
	update(0,0,n,pos);
	return (seg[0].pre*seg[0].ymax).val;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:120:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (seg[0].pre*seg[0].ymax).val;
                                  ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:126:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (seg[0].pre*seg[0].ymax).val;
                                  ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:132:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (seg[0].pre*seg[0].ymax).val;
                                  ^

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