Submission #1193277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193277		vivkostov	Horses (IOI15_horses)	C++20	17 / 100	405 ms	22840 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e9+7;
int ma[2000005],n,a[500005],b[500005],lamp[2000005];
long long int p[2000005];
vector<int>pos;
void build(int l,int r,int h)
{
    if(l==r)
    {
        p[h]=a[l];
        ma[h]=b[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,h*2);
    build(mid+1,r,h*2+1);
    ma[h]=max(ma[h*2],ma[h*2+1]);
    p[h]=p[h*2]*p[h*2+1];
    if(p[h]>=maxn)
    {
        lamp[h]=1;
        p[h]=p[h]%maxn;
    }
    else lamp[h]=max(lamp[h*2],lamp[h*2+1]);
}
void updateA(int l,int r,int q,int h,int st)
{
    if(l>q||r<q)return;
    if(l==r)
    {
        a[l]=st;
        p[h]=a[l];
        return;
    }
    int mid=(l+r)/2;
    updateA(l,mid,q,h*2,st);
    updateA(mid+1,r,q,h*2+1,st);
    p[h]=p[h*2]*p[h*2+1];
    if(p[h]>=maxn)
    {
        lamp[h]=1;
        p[h]=p[h]%maxn;
    }
    else lamp[h]=max(lamp[h*2],lamp[h*2+1]);
}
void updateB(int l,int r,int q,int h,int st)
{
    if(l>q||r<q)return;
    if(l==r)
    {
        b[l]=st;
        ma[h]=st;
        return;
    }
    int mid=(l+r)/2;
    updateB(l,mid,q,h*2,st);
    updateB(mid+1,r,q,h*2+1,st);
    ma[h]=max(ma[h*2],ma[h*2+1]);
}
int get_l(int l,int r,int h,long long int um)
{
    if(l==r)
    {
        if(um*p[h]>1e9)return l+1;
        return l;
    }
    int mid=(l+r)/2;
    if(lamp[h*2+1]||p[h*2+1]*um>1e9)return get_l(mid+1,r,h*2+1,um);
    else return get_l(l,mid,h*2,um*p[h*2+1]);
}
void get_pos(int l,int r,int q,int h)
{
    if(p[h]==1&&!lamp[h])return;
    if(l==r)
    {
        pos.push_back(l);
        return;
    }
    int mid=(l+r)/2;
    if(mid>=q)get_pos(l,mid,q,h*2);
    get_pos(mid+1,r,q,h*2+1);
}
long long int get_st(int l,int r,int ql,int qr,int h)
{
    if(l>qr||r<ql)return 0;
    if(l>=ql&&r<=qr)return p[h];
    int mid=(l+r)/2;
    return (get_st(l,mid,ql,qr,h*2)*get_st(mid+1,r,ql,qr,h*2+1))%maxn;
}
int get_ma(int l,int r,int ql,int qr,int h)
{
    if(l>qr||r<ql)return 0;
    if(l>=ql&&r<=qr)return ma[h];
    int mid=(l+r)/2;
    return max(get_ma(l,mid,ql,qr,h*2),get_ma(mid+1,r,ql,qr,h*2+1));
}
long long int resh()
{
    int to=get_l(1,n,1,1);
    get_pos(1,n,to,1);
    long long int otg=get_ma(1,n,1,n,1),seg=1,le=1;
    pos.push_back(n+1);
    for(int i=0;i<pos.size()-1;i++)
    {
        seg*=a[pos[i]];
        otg=max(otg,seg*get_ma(1,n,pos[i],pos[i+1]-1,1));
    }
    pos.clear();
    if(to!=1)le=get_st(1,n,1,to-1,1);
    return ((otg%maxn)*le)%maxn;
}
int init(int N, int X[], int Y[])
{
    n=N;
    for(int i=0;i<n;i++)
    {
        a[i+1]=X[i];
        b[i+1]=Y[i];
    }
    build(1,n,1);
	return resh();
}

int updateX(int po, int val)
{
    po++;
    updateA(1,n,po,1,val);
	return resh();
}

int updateY(int po, int val)
{
    po++;
    updateB(1,n,po,1,val);
	return resh();
}

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