Submission #16726

#	Time	Username	Problem	Language	Result	Execution time	Memory
16726		comet	Horses (IOI15_horses)	C++98	100 / 100	344 ms	54280 KiB

horses

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
//#include "horses.h"
using namespace std;
#define MOD (ll)(1e9+7)
typedef long long ll;
ll N,X[500010],Y[500010];
struct SegTree{
	struct node{
		ll L,R,E,p;
		node(){L=R=E=1;p=500001;}
		node(int pos,int val){
			L=E=val;
			R=1;
			p=pos;
		}

		void write(){
			printf("%lld %lld %lld %lld",p,L,R,E);
		}
	};
	vector<node> tree;
	int sz;
	void init(int n){
		for(sz=1;sz<n;sz<<=1);
		sz--;
		tree.resize(2*sz+10);
	}

	#define LL (x<<1)
	#define RR ((x<<1)+1)
	void update(int pos,int val){
		int x=pos+sz;
		tree[x]=node(pos,val);
		x>>=1;
		while(x){
			ll z=min(MOD,tree[LL].R*tree[RR].L);
/*
			printf("x=%d\n",x);
			printf("L-> ");tree[LL].write();puts("");
			printf("R-> ");tree[RR].write();puts("");
*/
			if(Y[tree[LL].p]<z*Y[tree[RR].p]){
				//puts("1");
				tree[x].p=tree[RR].p;
				tree[x].L=min(MOD,tree[LL].E*tree[RR].L);
				tree[x].R=tree[RR].R;
				tree[x].E=min(MOD,tree[LL].E*tree[RR].E);
			}
			else{
				//puts("2");
				tree[x].p=tree[LL].p;
				tree[x].L=tree[LL].L;
				tree[x].R=min(MOD,tree[LL].R*tree[RR].E);
				tree[x].E=min(MOD,tree[LL].E*tree[RR].E);
			}
			x>>=1;
		}
	}
	int query(){
		return tree[1].p;
	}
	#undef LL
	#undef RR
}horse;
struct MUL{
	vector<ll> tree;
	int sz;
	void init(int n){
		for(sz=1;sz<n;sz<<=1);
		sz--;
		tree.resize(2*sz+10,1);
	}
	void update(int x,int c){
		x+=sz;
		tree[x]=c;
		x>>=1;
		while(x){
			tree[x]=(tree[x*2]*tree[x*2+1])%MOD;
			x>>=1;
		}
	}
	ll query(int L,int R){
		L+=sz,R+=sz;
		ll ret=1;
		while(L<R){
			if(L&1)ret=(ret*tree[L++])%MOD;
			if(~R&1)ret=(ret*tree[R--])%MOD;
			L>>=1,R>>=1;
		}
		if(L==R)ret=(ret*tree[L])%MOD;
		return ret;
	}
}mul;
int init(int n, int x[], int y[]) {
	N=n;
	horse.init(n);
	mul.init(n);
	for(int i=0;i<n;i++){
		X[i+1]=x[i];
		Y[i+1]=y[i];
	}
	for(int i=1;i<=n;i++)horse.update(i,X[i]),mul.update(i,X[i]);
	//printf("pos=%d\n",horse.query());
	ll ret=mul.query(1,horse.query());
	return ret=(ret*Y[horse.query()])%MOD;
}

int updateX(int pos, int val) {
	pos++;
	X[pos]=val;
	horse.update(pos,val);
	mul.update(pos,val);
	//printf("updateX : pos=%d\n",horse.query());
	ll ret=mul.query(1,horse.query());
	ret=(ret*Y[horse.query()])%MOD;
	return ret;
}

int updateY(int pos, int val) {
	pos++;
	Y[pos]=val;
	horse.update(pos,X[pos]);
	//printf("updateY : pos=%d\n",horse.query());
	ll ret=mul.query(1,horse.query());
	ret=(ret*Y[horse.query()])%MOD;
	return ret;
}

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