Submission #1191005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191005		simona1230	Horses (IOI15_horses)	C++20	100 / 100	433 ms	53072 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

//static FILE *_inputFile, *_outputFile;

const int mod=1e9+7;
const int maxn=5*1e5+5;

long long n,x[maxn],y[maxn];
long long maxx[4*maxn],prod[4*maxn];

int qmax(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return maxx[i];
    int m=(l+r)/2;
    return max(qmax(i*2,l,m,ql,min(qr,m)),qmax(i*2+1,m+1,r,max(m+1,ql),qr));
}

long long qprod(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 1;
    if(ql<=l&&r<=qr)return prod[i];
    int m=(l+r)/2;
    return (qprod(i*2,l,m,ql,min(qr,m))*qprod(i*2+1,m+1,r,max(m+1,ql),qr))%mod;
}

set<int> s;

long long answer()
{
    if(n==1)return (x[0]*y[0])%mod;
    if(s.size()==0)return maxx[1];
    //for(auto it=s.begin();it!=s.end();it++)
    //    cout<<*it<<endl;
    auto it=s.end();
    long long curr=0,id=0,hh=0;
    while(it!=s.begin())
    {
        int nxt=n-1;
        if(it!=s.end())nxt=*it-1;

        it--;
        int i=*it;

        int h=qmax(1,0,n-1,i,nxt);
        //fprintf(_outputFile,"%d ",nxt);
        //cout<<"+ "<<h<<endl;
        if(curr<h)curr=h,id=i,hh=h;
        curr*=x[i];

        if(curr>1e9)break;
    }
    //cout<<id<<endl;

    return (qprod(1,0,n-1,0,id)*hh)%mod;
}

void umaxx(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        maxx[i]=vl;
        return;
    }
    int m=(l+r)/2;
    if(id<=m)umaxx(i*2,l,m,id,vl);
    else umaxx(i*2+1,m+1,r,id,vl);
    maxx[i]=max(maxx[i*2],maxx[i*2+1]);
}

void uprod(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        prod[i]=vl;
        return;
    }
    int m=(l+r)/2;
    if(id<=m)uprod(i*2,l,m,id,vl);
    else uprod(i*2+1,m+1,r,id,vl);
    prod[i]=(prod[i*2]*prod[i*2+1])%mod;
}

void build(int i,int l,int r)
{
    if(l==r)
    {
        maxx[i]=y[l];
        prod[i]=x[l];
        return;
    }
    int m=(l+r)/2;
    build(i*2,l,m);
    build(i*2+1,m+1,r);
    maxx[i]=max(maxx[i*2],maxx[i*2+1]);
    prod[i]=(prod[i*2]*prod[i*2+1])%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];
    build(1,0,n-1);
    for(int i=0;i<N;i++)
        if(x[i]!=1)s.insert(i);
        s.insert(0);

    return answer();
}

int updateX(int pos, int val)
{
    x[pos]=val;
    if(val==1&&pos)s.erase(pos);
    else s.insert(pos);
    uprod(1,0,n-1,pos,val);
	return answer();
}

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

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