Submission #1178445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178445		sleepntsheep	Horses (IOI15_horses)	C11	0 / 100	55 ms	19016 KiB

horses

#include "horses.h"
#include <stdio.h>

int n, t[1111111], r1[1111111], y[555555], r2[1111111];

int mul1(int i,int j){ return(i*1ll*j<1000000000)?i*j:1000000000; }
int mul2(int i,int j){ return i*1ll*j%1000000007; }

void pulr(int i){ r1[i]=mul1(r1[i*2],r1[i*2+1]); r2[i]=mul2(r2[i*2],r2[i*2+1]);}
int queryr(int l,int r){
	int z=1;
	for(l+=n,r+=n;l<r;l/=2,r/=2){
		if(l&1)z=mul1(z,r1[l++]);
		if(r&1)z=mul1(r1[--r],z);
	}
	return z;
}
int queryr2(int l,int r){
	int z=1;
	for(l+=n,r+=n;l<r;l/=2,r/=2){
		if(l&1)z=mul2(z,r2[l++]);
		if(r&1)z=mul2(r2[--r],z);
	}
	return z;
}
int mint(int a,int b){ if(a==-1)return b;if(b==-1)return a;return(queryr(a+1,b+1)*1ll*y[b]>=y[a])?b:a; }
void pult(int i){ t[i]=mint(t[i*2],t[i*2+1]); }
int queryt(int l,int r){
	int z=-1;
	for(l+=n,r+=n;l<r;l/=2,r/=2){
		if(l&1)z=mint(z,t[l++]);
		if(r&1)z=mint(t[--r],z);
	}
	return z;
}

int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<n;++i) t[i+n]=i, r1[i+n]=r2[i+n]=X[i], y[i]=Y[i];
	for(int i=n;--i;)pulr(i);
	for(int i=n;--i;)pult(i);
	return queryr2(0,1+t[1])*1ll*y[t[1]]%1000000007;
}

int updateX(int pos, int val) {
	int k=queryt(pos,n);
	r1[pos+n]=r2[pos+n]=val;
	for(int j=pos+n;j/=2;)pulr(j);
	for(int j=pos+k;j/=2;)pult(j);
	return queryr2(0,1+t[1])*1ll*y[t[1]]%1000000007;
}

int updateY(int pos, int val) {
	int k=queryt(pos,n);
	y[pos]=val;
	for(int j=pos+k;j/=2;)pult(j);
	return queryr2(0,1+t[1])*1ll*y[t[1]]%1000000007;
}

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