Submission #1190970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190970		DobromirAngelov	Horses (IOI15_horses)	C++20	0 / 100	303 ms	40600 KiB

horses

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

using namespace std;

const int MAXN=5e5+5;
const int MAXV=1e9;
const int MOD=1e9+7;

int n;
int a[MAXN];
int x[MAXN];

struct SegmentTree
{
	int tree[4*MAXN];

	void init()
	{
		fill(tree,tree+4*n,0);
	}

	void build(int node,int l,int r)
	{
		if(l==r)
		{
			tree[node]=a[l];
			return;
		}
		int mid=(l+r)/2;
		build(2*node,l,mid);
		build(2*node+1,mid+1,r);
		tree[node]=max(tree[2*node],tree[2*node+1]);
	}

	void update(int node,int l,int r,int pos,int val)
	{
		if(l==r)
		{
			tree[node]=val;
			return;
		}
		int mid=(l+r)/2;
		if(pos<=mid) update(2*node,l,mid,pos,val);
		if(mid<pos) update(2*node+1,mid+1,r,pos,val);
		tree[node]=max(tree[2*node], tree[2*node+1]);
	}

	int query(int node,int l,int r,int ql,int qr)
	{
		if(ql<=l && r<=qr) return tree[node];
		int ret=0;
		int mid=(l+r)/2;
		if(ql<=mid) ret=max(ret, query(2*node,l,mid,ql,qr));
		if(mid<qr) ret=max(ret, query(2*node+1,mid+1,r,ql,qr));
		return ret;
	}

	void update(int pos,int val)
	{
		update(1,1,n,pos,val);
	}

	int query(int l,int r)
	{
		return query(1,1,n,l,r);
	}
};
SegmentTree tree;

long long prod=1;
set<int> mlts;

int fastPow(long long x,int pwr)
{
	long long ret=1;
	while(pwr)
	{
		if(pwr&1) ret=ret*x%MOD;
		pwr/=2;
		x=x*x%MOD;
	}
	return ret;
}

int inv(int x)
{
	return fastPow(x,MOD-2);
}

int query()
{
	vector<int> pos;
	long long tmp=1;
	for(auto it=mlts.rbegin();it!=mlts.rend();it++)
	{
		if(tmp>=MAXV) break;
		pos.push_back((*it));
		tmp*=x[(*it)];
	}
	reverse(pos.begin(), pos.end());
	long long T=prod*inv(tmp)%MOD;
//for(auto x: pos) cout<<x<<" "; cout<<endl;
	vector<pair<int,int> > cur;
	for(int i=0;i<pos.size();i++)
	{
		int r=((i+1<pos.size()) ? pos[i+1]-1 : n);
		cur.push_back({x[pos[i]], tree.query(pos[i],r)});
	}
	long long ret=1;
	tmp=1;
	for(int i=0;i<cur.size();i++)
	{
		tmp*=cur[i].first;
		if(tmp>LLONG_MAX/cur[i].second) cout<<1/0<<endl;
		ret=max(ret, tmp*cur[i].second);
	}

	return T*ret%MOD;
/*
	int bst=a[n];
	int ret=prod;
	long long curProd=x[n];
	for(int i=pos.size()-1;i>=0;i--)
	{
		if(pos[i]==n) continue;
		int l=pos[i];
		int r=(i+1<pos.size() ? pos[i+1]-1 : n-1);
		int mx=tree.query(l,r);
		if(mx>curProd*bst)
		{
			ret=ret*inv(curProd);
			bst=mx;
			curProd=1;
		}
		curProd*=x[l];
	}
	return 1LL*ret*bst%MOD;
	*/
}

int init(int N, int X[], int Y[]) 
{
	n=N;
	for(int i=1;i<=n;i++) a[i]=Y[i-1];
	for(int i=1;i<=n;i++) x[i]=X[i-1];

	prod=1;
	for(int i=1;i<=n;i++)
	{
		if(x[i]>1) mlts.insert(i);
		prod=prod*x[i]%MOD;
	}
	tree.init();
	tree.build(1,1,n);

	return query();
}

int updateX(int pos, int val) 
{
	pos++;
	if(x[pos]==1) mlts.insert(pos);
	else mlts.erase(pos);
	mlts.insert(1);
	prod=prod*inv(x[pos])%MOD;
	x[pos]=val;
	prod=prod*x[pos]%MOD;
	return query();
}

int updateY(int pos, int val) 
{
	pos++;
	a[pos]=val;
	tree.update(pos,val);
	return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:115:56: warning: division by zero [-Wdiv-by-zero]
  115 |                 if(tmp>LLONG_MAX/cur[i].second) cout<<1/0<<endl;
      |                                                       ~^~

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