Submission #66963

#	Time	Username	Problem	Language	Result	Execution time	Memory
66963		MKopchev	Horses (IOI15_horses)	C++14	100 / 100	1006 ms	252472 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nmax=5e5+42,mod=1e9+7,inf=1e9+42;
int n,x[nmax],y[nmax];
set<int> non_zero;
long long tree_x[4*nmax],tree_y[4*nmax];
void build_x(int node,int l,int r)
{
    if(l==r)
    {
    tree_x[node]=x[l];
    return;
    }
    int av=(l+r)/2;
    build_x(node*2,l,av);
    build_x(node*2+1,av+1,r);
    tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
void update_x(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {

    tree_x[node]=val;
    return;
    }
    int av=(l+r)/2;
    if(pos<=av)update_x(node*2,l,av,pos,val);
    else update_x(node*2+1,av+1,r,pos,val);
    tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
int query_x(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree_x[node];
    int av=(l+r)/2;
    long long ans=1;
    if(lq<=av)ans=ans*query_x(node*2,l,av,lq,min(av,rq))%mod;
    if(av<rq)ans=ans*query_x(node*2+1,av+1,r,max(av+1,lq),rq)%mod;
    return ans;
}

void build_y(int node,int l,int r)
{
    if(l==r)
    {
    tree_y[node]=y[l];
    return;
    }
    int av=(l+r)/2;
    build_y(node*2,l,av);
    build_y(node*2+1,av+1,r);
    tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
void update_y(int node,int l,int r,int pos,int val)
{
    assert(l<=pos&&pos<=r);
    if(l==r)
    {
    tree_y[node]=val;
    return;
    }
    int av=(l+r)/2;
    if(pos<=av)update_y(node*2,l,av,pos,val);
    else update_y(node*2+1,av+1,r,pos,val);
    tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
int query_y(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree_y[node];
    int av=(l+r)/2;
    int ans=0;
    if(lq<=av)ans=max(ans,query_y(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ans=max(ans,query_y(node*2+1,av+1,r,max(av+1,lq),rq));
    return ans;
}


bool bigger(long long a,long long b,long long c)
{
    return a>=(c+b-1)/b;
}
int active[nmax],ind=0;
pair<int,int> slow()
{
    double sum=0,maxi=0,now;
    int ind=0;
    for(int i=0;i<n;i++)
    {
        sum=sum+log10(1.0*x[i]);
        now=sum+log10(1.0*y[i]);
        if(now>maxi+1.0/1e9)
        {
            maxi=now;
            ind=i;
        }
    }
    long long res=y[ind];
    for(int i=0;i<=ind;i++)
    {
        res=res*x[i]%mod;
    }
    return {res,ind};
}
void test(long long a,long long b,long long &c,long long &d)
{
    double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
    if(p>q+1.0/1e9)
    {
        c=a;
        d=b;
    }
}
int query()
{
    if(non_zero.size()==0)return query_y(1,0,n-1,0,n-1);
    long long prod=1,maxi=1;
    int last=n,pos=-1;
    ind=0;
    for(auto k:non_zero)
    {
        pos=-k;
        active[++ind]=pos;
        prod=prod*x[pos];
        if(prod>inf)break;
    }
    reverse(active+1,active+ind+1);
    //cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
    prod=1;
    long long p1,b1=1,b2=1;
    for(int i=1;i<ind;i++)
    {
        prod=prod*x[active[i]];
        //cout<<"q "<<query_y(1,0,n-1,active[i],active[i+1]-1)<<endl;
        p1=query_y(1,0,n-1,active[i],active[i+1]-1);
        test(prod,p1,b1,b2);
    }

    if(ind==non_zero.size())
    {
        if(active[1]!=0)maxi=max(maxi,1LL*query_y(1,0,n-1,0,active[1]-1));
    }

    test(maxi,1,b1,b2);

    //cout<<maxi<<endl;

    long long mult=1;
    if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);

    long long a=prod*x[active[ind]];
    long long b=query_y(1,0,n-1,active[ind],n-1);

    test(a,b,b1,b2);
    long long ret=mult%mod*(b1%mod)%mod*(b2%mod)%mod;
    /*
    if(n<=1000)
    {
        if(ret!=slow().first)
        {
            cout<<a<<" "<<b<<" "<<maxi<<" "<<mult<<endl;
            cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
            cout<<ret<<endl;
            for(int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;
            cout<<endl;
            for(int i=0;i<n;i++)cout<<y[i]<<" ";cout<<endl;
            cout<<slow().first<<" "<<slow().second<<" "<<x[slow().second]<<" "<<y[slow().second]<<endl;
            system("pause");
            if(bigger(a,b,maxi))
            {
            assert(slow().second>=active[1]);
            while(1);
            }
            else assert(0==1);
        }

    }
    */
    return ret;
}

int init(int N,int X[],int Y[])
{
    n=N;
    for(int i=0;i<N;i++)x[i]=X[i],y[i]=Y[i];
    for(int i=0;i<N;i++)
        if(x[i]!=1)
        {
        non_zero.insert(-i);
        }
    build_x(1,0,n-1);
    build_y(1,0,n-1);
    return query();
}
int updateX(int pos,int val)
{
    if(x[pos]!=1)non_zero.erase(-pos);
    x[pos]=val;
    if(x[pos]!=1)non_zero.insert(-pos);
    update_x(1,0,n-1,pos,val);
    return query();
}
int updateY(int pos,int val)
{
    y[pos]=val;
    update_y(1,0,n-1,pos,val);
    return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query_x(int, int, int, int, int)':
horses.cpp:35:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(l==lq&&r==rq)return tree_x[node];
                            ~~~~~~~~~~~^
horses.cpp:40:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ans;
            ^~~
horses.cpp: In function 'int query_y(int, int, int, int, int)':
horses.cpp:70:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(l==lq&&r==rq)return tree_y[node];
                            ~~~~~~~~~~~^
horses.cpp: In function 'std::pair<int, int> slow()':
horses.cpp:87:9: warning: declaration of 'ind' shadows a global declaration [-Wshadow]
     int ind=0;
         ^~~
horses.cpp:83:18: note: shadowed declaration is here
 int active[nmax],ind=0;
                  ^~~
horses.cpp: In function 'void test(long long int, long long int, long long int&, long long int&)':
horses.cpp:107:24: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                        ^
horses.cpp:107:37: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                                     ^
horses.cpp:107:52: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                                                    ^
horses.cpp:107:65: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                                                                 ^
horses.cpp: In function 'int query()':
horses.cpp:139:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind==non_zero.size())
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:149:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:179:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ret;
            ^~~
horses.cpp:118:9: warning: unused variable 'last' [-Wunused-variable]
     int last=n,pos=-1;
         ^~~~

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