Submission #56749

#	Time	Username	Problem	Language	Result	Execution time	Memory
56749		Bodo171	Horses (IOI15_horses)	C++14	100 / 100	1052 ms	255080 KiB

horses

#include "horses.h"
#include <iostream>
#include <set>
#include <climits>
using namespace std;
const int nmax=500005;
set<int> s;
set<int>::iterator it;
const long long mod=1000*1000*1000+7;
long long pr[4*nmax];
int arb[4*nmax];
int bun[nmax],v[nmax];
int mx,x,y,value,poz,st,dr,n,lg,ok,lst,M;
long long ans;
void U(int nod,int l,int r)
{
    if(l==r)
    {
        pr[nod]=value;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) U(2*nod,l,m);
    else U(2*nod+1,m+1,r);
    pr[nod]=(1LL*pr[2*nod]*pr[2*nod+1])%mod;
}
void Q(int nod,int l,int r)
{
    if(st<=l&&r<=dr)
    {
        ans=(1LL*ans*pr[nod])%mod;
        return;
    }
    int m=(l+r)/2;
    if(st<=m) Q(2*nod,l,m);
    if(m<dr) Q(2*nod+1,m+1,r);
}
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod]=value;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r)
{
    if(st<=l&&r<=dr)
    {
        M=max(M,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m);
    if(m<dr) query(2*nod+1,m+1,r);
}
int qry(int S,int D)
{
    st=S;dr=D;M=0;
    query(1,1,n);
    return M;
}
int get_mx()
{
    long long opt=0;
    it=s.lower_bound(n+1);
    lg=32;mx=0;ok=1;poz=n;lst=n+1;
    for(int i=1;i<=lg&&it!=s.begin()&&ok;i++)
    {
        it--;
        x=v[(*it)-1];y=qry((*it),lst-1);
        if(y>mx) mx=y,poz=(*it),opt=y;
        if(mx!=0&&x>INT_MAX/mx) ok=0;
        else mx*=x;
        lst=(*it);
    }
    st=1;dr=poz;ans=1;
    Q(1,1,n);
    ans=(1LL*ans*opt)%mod;
    return ans;
}
int init(int N, int X[], int Y[]) {
    n=N;
    for(int i=0;i<N;i++)
    {
        poz=i+1;value=X[i];v[i]=X[i];
        U(1,1,n);
    }
    for(int i=0;i<N;i++)
    {
        poz=i+1;value=Y[i];
        update(1,1,n);
    }
    s.insert(n+1);lst=N;
    for(int i=N-1;i>=0;i--)
       if(X[i]!=1)
    {
        s.insert(i+1);
        bun[i+1]=qry(i+1,lst);
        lst=i;
    }
    if(s.find(1)==s.end())
    {
        bun[1]=qry(1,n);
        s.insert(1);
    }
	return get_mx();
}

int updateX(int pos, int val) {
    poz=pos+1;value=val;
    if(v[poz-1]!=1)
    {
        s.erase(poz);
    }
    U(1,1,n);
    v[poz-1]=val;
    if(val!=1)
    {
        s.insert(poz);
    }
    bun[poz]=qry(poz,(*s.upper_bound(poz))-1);
    if(s.find(1)==s.end())
    {
        bun[1]=qry(1,n);
        s.insert(1);
    }
	return get_mx();
}

int updateY(int pos, int val) {

    poz=pos+1;value=val;
    update(1,1,n);
    it=s.upper_bound(poz);
    if(it!=s.begin())
    {
        it--;
        bun[(*it)]=qry((*it),(*s.upper_bound((*it)))-1);
    }
    bun[1]=qry(1,n);
	return get_mx();
}

Compilation message (stderr)

horses.cpp: In function 'int get_mx()':
horses.cpp:84:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ans;
            ^~~

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