Submission #154748

#	Time	Username	Problem	Language	Result	Execution time	Memory
154748		dennisstar	Horses (IOI15_horses)	C++11	0 / 100	1549 ms	33644 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int N, X[500010], Y_[500010];
set<pii, greater<pii> > S;

const ll MAX=1e9+7;
ll mypow(int n)
{
	int i=30;
	ll ret=1;
	for (; i>=0; i--) {
		ret=ret*ret%MAX;
		if ((1<<i)&(MAX-2)) ret=ret*n%MAX;
	}
	return ret;
}
ll mul=1;

struct seg{
	vector<int> Y;
	int initF(int ind, int i, int dx, int dy) {
		if (dx>dy||ind<dx||dy<ind) return Y[i];
		if (dx==dy&&dx==ind) {
			Y[i]=Y_[ind];
			return Y[i];
		}
		int ret=0, md=(dx+dy)/2;
		ret=max(ret, initF(ind, i*2, dx, md));
		ret=max(ret, initF(ind, i*2+1, md+1,dy));
		Y[i]=ret;
		return Y[i];
	}
	void init() {
		Y.resize(N*3);
		for (int i=0; i<N; i++) initF(i, 1, 0, N-1);
	}
	int mx(int s, int e, int i, int dx, int dy) {
		if (dx>dy||dy<s||e<dx) return 0;
		if (s<=dx&&dy<=e) return Y[i];
		if (dx==dy) return 0;
		int md=(dx+dy)/2;
		int mx1=mx(s,e,i*2,dx,md), mx2=mx(s,e,i*2+1,md+1,dy);
		return max(mx1, mx2); 
	}
}Seg;

ll getAns()
{
	//puts("OK getANS");
	set<pii, greater<pii> >::iterator it;
	ll now=1, ymx;
	ll mx1=0, mx2=1;
	ll ret=1;
	for (it=S.begin(); it!=S.end(); ++it) {
		ymx=Seg.mx((*it).first, (*it).second, 1, 0, N-1);
		if (mx1*now<ymx*mx2) {
			ret=mul*mypow((int)now)%MAX;
			ret=ret*ymx%MAX;
			mx1=ymx; mx2=now;
		}
		//printf("%lld %lld %lld\n", now, ret, ymx);
		now*=X[(*it).first];
		if (now>(1ll<<30)) break;
	}
	return ret;
}

int init(int N_, int x[], int y[]) {
	for (int i=0; i<N; i++) X[i]=x[i], Y_[i]=y[i];
	N=N_;
	for (int i=0; i<N; i++) mul=mul*x[i]%MAX;
	Seg.init();
	for (int i=N-1; i>=0; i--) {
		int j;
		for (j=i; j; j--) {if (x[j]!=1) break;}
		S.insert({j,i});
		i=j;
		if (i<0) assert(false);
	}
	//for (auto it=S.begin(); it!=S.end(); ++it) printf("{%d, %d} ", (*it).first, (*it).second);
	return (int)getAns();
}

int updateX(int pos, int val) {
	//puts("OK X");
	mul=mul*mypow(X[pos])%MAX; mul=mul*val%MAX;
	set<pii, greater<pii> >::iterator it, it1;
	if (X[pos]==1&&val!=1) {
		it=S.lower_bound({pos,pos});
		while ((*it).second<pos) ++it;
		while ((*it).first>pos) --it;
		if ((*it).first<pos&&pos<=(*it).second) {
			pii pi;
			pi=(*it);
			S.erase(it);
			S.insert({pi.first, pos-1}); S.insert({pos, pi.second});
		}
		//else assert(false);
	}
	else if (X[pos]!=1&&val==1) {
		it=S.lower_bound({pos,pos});
		while ((*it).second<pos) ++it;
		while ((*it).first>pos) --it;
		it1=it; it1++;
		pii pi={(*it1).first, (*it).second};
		pii pi1=(*it1), pi2=(*it);
		if ((*it).first==pos) {
			S.erase(pi1); S.erase(pi2);
			S.insert(pi);
		}
		//else assert(false);
	}
	X[pos]=val;
	return (int)getAns();
}

int updateY(int pos, int val) {
	//puts("OK Y");
	Y_[pos]=val;
	Seg.initF(pos, 1, 0, N-1);
	return (int)getAns();
}

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