Submission #1190981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190981		simona1230	Horses (IOI15_horses)	C++20	0 / 100	425 ms	52268 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 0;
    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++)
    //    fprintf(_outputFile,"%d ",*it);
    auto it=s.end();
    long long curr=0,id=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);
        if(curr<h)curr=h;
        curr*=x[i];
        id=i;

        if(curr>1e9)break;
    }

    if(id==0)return curr%mod;
    return curr%mod*qprod(1,0,n-1,0,id)%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);

    return answer();
}



int updateX(int pos, int val)
{
    x[pos]=val;
    if(val==1)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: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23