Submission #66954

#	Time	Username	Problem	Language	Result	Execution time	Memory
66954		MKopchev	Horses (IOI15_horses)	C++14	37 / 100	657 ms	49696 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nmax=5e5+42,mod=1e9+7,inf=1e9;
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)
{
    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=1;
    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;
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;
    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;
        maxi=max(maxi,prod*query_y(1,0,n-1,active[i],active[i+1]-1));
    }

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

    //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);

    if(bigger(a,b,maxi))return a%mod*b%mod*mult%mod;
    return maxi%mod*mult%mod;
}

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();
}
/*
int X[]={2,1,3};
int Y[]={3,4,1};
int main()
{
    cout<<init(3,X,Y)<<endl;
    cout<<updateY(1,2)<<endl;
}
*/

Compilation message (stderr)

horses.cpp: In function 'int query_x(int, int, int, int, int)':
horses.cpp:34: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:39: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:68: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 'int query()':
horses.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind==non_zero.size())
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:113: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:118:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(bigger(a,b,maxi))return a%mod*b%mod*mult%mod;
                                ~~~~~~~~~~~~~~~~^~~~
horses.cpp:119:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return maxi%mod*mult%mod;
            ~~~~~~~~~~~~~^~~~
horses.cpp:86:9: warning: unused variable 'last' [-Wunused-variable]
     int last=n,pos=-1;
         ^~~~

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