제출 #837292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837292		oscar1f	말 (IOI15_horses)	C++17	17 / 100	185 ms	56464 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"

using namespace std;
using ll=long long;

const ll MAX_VAL=500*1000+5,DECA=(1<<19),MODU=1000*1000*1000+7;
ll nbVal,rep;
ll multi[MAX_VAL],benef[DECA];
ll arbreMax[2*DECA],arbreProd[2*DECA];
set<ll> listeInter;

ll calcMax(ll deb,ll fin) {
	if (deb==fin) {
		return arbreMax[deb];
	}
	if (deb%2==1) {
		return max(arbreMax[deb],calcMax(deb+1,fin));
	}
	if (fin%2==0) {
		return max(arbreMax[fin],calcMax(deb,fin-1));
	}
	return calcMax(deb/2,fin/2);
}

ll calcProd(ll deb,ll fin) {
	if (deb==fin) {
		return arbreProd[deb];
	}
	if (deb%2==1) {
		return (arbreProd[deb]*calcProd(deb+1,fin))%MODU;
	}
	if (fin%2==0) {
		return (arbreProd[fin]*calcProd(deb,fin-1))%MODU;
	}
	return calcProd(deb/2,fin/2);
}

void majMax(ll pos,ll val) {
	benef[pos]=val;
	pos+=DECA;
	arbreMax[pos]=val;
	while (pos>1) {
		pos/=2;
		arbreMax[pos]=max(arbreMax[2*pos],arbreMax[2*pos+1]);
	}
}

void majProd(ll pos,ll val) {
	multi[pos]=val;
	pos+=DECA;
	arbreProd[pos]=val;
	while (pos>1) {
		pos/=2;
		arbreProd[pos]=(arbreProd[2*pos]*arbreProd[2*pos+1])%MODU;
	}
}

void calc() {
	auto it=listeInter.end();
	it--;
	ll prodCour=1,meilleur=0;
	while ((*it)!=-1 and prodCour*multi[(*it)]<MODU) {
		prodCour*=multi[(*it)];
		meilleur=max(meilleur,calcMax(DECA+(*it),DECA+nbVal-1));
		meilleur*=multi[(*it)];
		it--;
	}
	if ((*it)==-1) {
		ll maxi=calcMax(DECA,DECA+nbVal-1);
		//cout<<meilleur<<" "<<maxi<<endl;
		if (meilleur>maxi) {
			rep=meilleur%MODU;
		}
		else {
			rep=maxi;
		}
	}
	else {
		it++;
		meilleur%=MODU;
		if ((*it)>0) {
			meilleur*=calcProd(DECA,DECA+(*it)-1);
		}
		rep=meilleur%MODU;
	}
	//cout<<rep<<endl;
}

int init(int N, int X[], int Y[]) {
	nbVal=N;
	for (ll i=0;i<nbVal;i++) {
		multi[i]=X[i];
		benef[i]=Y[i];
	}
	for (ll i=0;i<2*DECA;i++) {
		arbreProd[i]=1;
	}
	for (ll i=0;i<nbVal;i++) {
		arbreProd[DECA+i]=multi[i];
		arbreMax[DECA+i]=benef[i];
	}
	for (ll i=DECA-1;i>0;i--) {
		arbreProd[i]=(arbreProd[2*i]*arbreProd[2*i+1])%MODU;
		arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]);
	}
	for (ll i=0;i<nbVal;i++) {
		if (multi[i]>1) {
			listeInter.insert(i);
		}
	}
	listeInter.insert(-1);
	//cout<<calc()<<endl;
	calc();
	return (int)rep;
}

int updateX(int pos, int val) {	
	if (multi[pos]>1) {
		listeInter.erase(pos);
	}
	majProd(pos,val);
	if (multi[pos]>1) {
		listeInter.insert(pos);
	}
	/*for (auto i:listeInter) {
		cout<<i<<" ";
	}
	cout<<": ";*/
	calc();
	return (int)rep;
}

int updateY(int pos, int val) {
	majMax(pos,val);
	calc();
	return (int)rep;
}

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