Submission #1219370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219370		LeonidCuk	Horses (IOI15_horses)	C++20	0 / 100	1018 ms	67952 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
vector<long long>stx,sty,vx,vy;
set<long long>s;
long long mod=1e9+7;
int n;
void updatey(int i,int l,int r,int x,int k)
{
    if(l==r)sty[i]=k;
    else
    {
        int m=(l+r)/2;
        if(x<=m)updatey(2*i,l,m,x,k);
        else updatey(2*i+1,m+1,r,x,k);
        sty[i]=max(sty[2*i],sty[2*i+1]);
    }
}
void updatex(int i,int l,int r,int x,int k)
{
    if(l==r)stx[i]=k;
    else
    {
        int m=(l+r)/2;
        if(x<=m)updatex(2*i,l,m,x,k);
        else updatex(2*i+1,m+1,r,x,k);
        stx[i]=(stx[2*i]*stx[2*i+1])%mod;
    }
}
long long getx(int i,int l,int r,int tl,int tr)
{
    if(tl>r||l>tr||l>r)return 1;
    if(tl<=l&&r<=tr)return stx[i];
    int m=(l+r)/2;
    return (getx(2*i,l,m,tl,tr)*getx(2*i+1,m+1,r,tl,tr))%mod;
}
long long gety(int i,int l,int r,int tl,int tr)
{
    if(tl>r||l>tr||l>r)return 1;
    if(tl<=l&&r<=tr)return sty[i];
    int m=(l+r)/2;
    return max(gety(2*i,l,m,tl,tr),gety(2*i+1,m+1,r,tl,tr));
}
long long vrni()
{
    if(s.size()==0)return gety(1,0,n-1,0,n-1);
    long long sum=1,b=n,res=stx[1];
    for(auto it=s.rbegin();it!=s.rend();it++)
    {
        int x=*it;
        long long a=gety(1,0,n-1,x,b-1);
        if(a>sum)
        {
            res=(getx(1,0,n-1,0,x)*a)%mod;
            sum=1;
        }
        sum=sum*vx[x];
        b=x;
        if(sum>mod)break;
    }
    if(sum<mod)
    {
        long long a=gety(1,0,n-1,0,b-1);
        if(a>sum)
        {
            res=a;
        }
    }
    return res;
}
int init(int N, int x1[], int y1[])
{
    n=N;
    stx.resize(4*n+1);
    sty.resize(4*n+1);
    for(int i=0;i<n;i++)
    {
        if(x1[i]!=1)s.insert(i);
        updatex(1,0,n-1,i,x1[i]);
        updatey(1,0,n-1,i,y1[i]);
        vx.push_back(x1[i]);
        vy.push_back(y1[i]);
    }
    return vrni();
}
int updateX(int pos, int val)
{
    updatex(1,0,n-1,pos,val);
    if(vx[pos]==1&&val>1)
    {
        s.insert(pos);
    }
    else if(vx[pos]>1&&val==1)s.erase(pos);
    vx[pos]=val;
    return vrni();
}
int updateY(int pos, int val)
{
    updatey(1,0,n-1,pos,val);
    vy[pos]=val;
    return vrni();
}

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