Submission #1190982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190982		DobromirAngelov	Horses (IOI15_horses)	C++20	100 / 100	643 ms	38592 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 x[MAXN];

struct SegmentTree
{
	int tree[4*MAXN];

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

	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> big;

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<pair<int,int> > cur;
    long long curProd=prod;
    long long tmp=1;
    int r=n;
    for(auto it=big.rbegin(); it!=big.rend(); it++)
    {
        int ind=(*it);
        if(tmp*x[ind]>MAXV)
        {
            cur.push_back({1,tree.query(ind,r)});
            break;
        }
        curProd=curProd*inv(x[ind])%MOD;
        tmp*=x[ind];
        cur.push_back({x[ind], tree.query(ind,r)});
        r=ind-1;
    }
    reverse(cur.begin(), cur.end());
    long long ret=1;
    long long pref=1;
    for(auto p: cur)
    {
        pref*=p.first;
        ret=max(ret, pref*p.second);
    }
    ret%=MOD;
    return ret*curProd%MOD;
}

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

    big.insert(1);
    for(int i=2;i<=n;i++)
    {
        if(x[i]>1) big.insert(i);
    }
    prod=1;
    for(int i=1;i<=n;i++) prod=prod*x[i]%MOD;

    return query();
}

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

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

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