Submission #91037

#	Time	Username	Problem	Language	Result	Execution time	Memory
91037		faustaadp	Horses (IOI15_horses)	C++17	100 / 100	865 ms	269016 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,has=0,hz=1,x[505050],y[505050],PS=1,mo=1000000007,K,n;
ll ST[2020202],ST2[2020202],te,a[505050],ST3[2020202];
void upd(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(aa==bb)
        ST[ee]=dd;
    else
    {
        ll ce=(aa+bb)/2;
        if(cc<=ce)upd(aa,ce,cc,dd,ee*2);
        else upd(ce+1,bb,cc,dd,ee*2+1);
        ST[ee]=(ST[ee*2]*ST[ee*2+1])%mo;
    }
}
void upd2(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(aa==bb)
        ST2[ee]=dd;
    else
    {
        ll ce=(aa+bb)/2;
        if(cc<=ce)upd2(aa,ce,cc,dd,ee*2);
        else upd2(ce+1,bb,cc,dd,ee*2+1);
        ST2[ee]=(ST2[ee*2]+ST2[ee*2+1]);
    }
}
void upd3(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(aa==bb)
        ST3[ee]=dd;
    else
    {
        ll ce=(aa+bb)/2;
        if(cc<=ce)upd3(aa,ce,cc,dd,ee*2);
        else upd3(ce+1,bb,cc,dd,ee*2+1);
        ST3[ee]=max(ST3[ee*2],ST3[ee*2+1]);
    }
}
ll cari(ll aa,ll bb,ll cc,ll ee)
{
    if(aa==bb)
    {
        a[++te]=aa;
    }
    else
    {
        ll ce=(aa+bb)/2;
        if(ST2[ee*2+1]==0)
            cari(aa,ce,cc,ee*2);
        else
        {
            if(cc<=ST2[ee*2+1])cari(ce+1,bb,cc,ee*2+1);
            else
            {
                cari(aa,ce,cc-ST2[ee*2+1],ee*2);
                cari(ce+1,bb,ST2[ee*2+1],ee*2+1);
            }
        }

    }
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(bb<cc||dd<aa)return 1LL;
    else if(cc<=aa&&bb<=dd)return ST[ee];
    else
    {
        ll ce=(aa+bb)/2;
        return (que(aa,ce,cc,dd,ee*2)*que(ce+1,bb,cc,dd,ee*2+1))%mo;
    }
}
ll que3(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(bb<cc||dd<aa)return 0LL;
    else if(cc<=aa&&bb<=dd)return ST3[ee];
    else
    {
        ll ce=(aa+bb)/2;
        return max(que3(aa,ce,cc,dd,ee*2),que3(ce+1,bb,cc,dd,ee*2+1));
    }
}
ll powo(ll aa,ll bb)
{
    if(bb==0)return 1LL;
    else
    {
        ll tem=powo(aa,bb/2);
        tem=(tem*tem)%mo;
        if(bb%2==1)tem=(tem*aa)%mo;
        return tem;
    }
}
ll com(ll aa,ll bb)
{
    return (que(0,n-1,0,aa,1)*bb)%mo;
}
ll jaw()
{
    te=0;
    //memset(a,-1,sizeof(a));
    cari(0,n-1,min(32LL,ST2[1]),1);
   // sort(a+1)
    ll opt=a[te],hz=y[a[te]],ii,Z=x[a[te]];
    //for(ii=1;ii<=te;ii++)   cout<<ii<<" "<<a[ii]<<"\n";
    for(ii=te-1;ii>=1;ii--)
    {
        if(Z>1000000000)return com(opt,hz);
        //cout<<que3(0,n-1,a[ii],a[ii+1]-1,1)<<"\n";
        if(que3(0,n-1,a[ii],a[ii+1]-1,1)>Z*hz)
        {
            opt=a[ii];
            hz=que3(0,n-1,a[ii],a[ii+1]-1,1);
            Z=1;
        }
        Z*=x[a[ii]];
    }
    return com(opt,hz);
}
int init(int N, int X[], int Y[])
{
    n=N;
    for(i=0;i<N;i++)x[i]=X[i];
    for(i=0;i<N;i++)upd(0,n-1,i,x[i],1);
    for(i=0;i<N;i++)upd2(0,n-1,i,((x[i]>1)||(i==0||i==(n-1))),1);
    for(i=0;i<N;i++)y[i]=Y[i];
    for(i=0;i<N;i++)upd3(0,n-1,i,y[i],1);
    //K=max(0LL,n-32LL);
    K=0;
	return jaw();
}

int updateX(int pos, int val)
{
    upd(0,n-1,pos,val,1);
    upd2(0,n-1,pos,((val>1)||(pos==0||pos==(n-1))),1);
    x[pos]=val;
	return jaw();
}

int updateY(int pos, int val)
{
    y[pos]=val;
    upd3(0,n-1,pos,val,1);
	return jaw();
}

Compilation message (stderr)

horses.cpp: In function 'long long int cari(long long int, long long int, long long int, long long int)':
horses.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'long long int jaw()':
horses.cpp:111:18: warning: declaration of 'hz' shadows a global declaration [-Wshadow]
     ll opt=a[te],hz=y[a[te]],ii,Z=x[a[te]];
                  ^~
horses.cpp:9:12: note: shadowed declaration is here
 ll i,has=0,hz=1,x[505050],y[505050],PS=1,mo=1000000007,K,n;
            ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:137:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return jaw();
         ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:145:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return jaw();
         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:152:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return jaw();
         ~~~^~

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