Submission #620071

#	Time	Username	Problem	Language	Result	Execution time	Memory
620071		Bench0310	Horses (IOI15_horses)	C++17	100 / 100	673 ms	65524 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;
typedef long long ll;

const ll mod=1000000007;
const ll lim=1000000000;
ll mul(ll a,ll b){return (a*b)%mod;};

const int N=500005;
int n;
ll x[N];
ll y[N];
ll treex[4*N];
ll treey[4*N];
set<int> s;

void pull(int idx)
{
    treex[idx]=mul(treex[2*idx],treex[2*idx+1]);
    treey[idx]=max(treey[2*idx],treey[2*idx+1]);
}

void build(int idx,int l,int r)
{
    if(l==r)
    {
        treex[idx]=x[l];
        treey[idx]=y[l];
    }
    else
    {
        int m=(l+r)/2;
        build(2*idx,l,m);
        build(2*idx+1,m+1,r);
        pull(idx);
    }
}

void update(int idx,int l,int r,int pos,ll val,int t)
{
    if(l==r)
    {
        if(t==0) treex[idx]=val;
        else treey[idx]=val;
    }
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,val,t);
        else update(2*idx+1,m+1,r,pos,val,t);
        pull(idx);
    }
}

ll query(int idx,int l,int r,int ql,int qr,int t)
{
    if(ql>qr) return (1-t);
    if(l==ql&&r==qr) return (t==0?treex[idx]:treey[idx]);
    int m=(l+r)/2;
    ll one=query(2*idx,l,m,ql,min(qr,m),t);
    ll two=query(2*idx+1,m+1,r,max(ql,m+1),qr,t);
    if(t==0) return mul(one,two);
    else return max(one,two);
}

int solve()
{
    bool rm=0;
    if(s.find(0)==s.end())
    {
        rm=1;
        s.insert(0);
    }
    ll best=0;
    int nxt=n;
    for(auto it=s.rbegin();it!=s.rend();it++)
    {
        int p=(*it);
        best=x[p]*max(best,query(1,0,n-1,p,nxt-1,1));
        nxt=p;
        if(best>=lim) break;
    }
    if(rm) s.erase(0);
    return int(mul(best%mod,query(1,0,n-1,0,nxt-1,0)));
}

int init(int tn,int X[],int Y[])
{
    n=tn;
    for(int i=0;i<n;i++)
    {
        x[i]=X[i];
        y[i]=Y[i];
        if(x[i]>1) s.insert(i);
    }
    build(1,0,n-1);
    return solve();
}

int updateX(int pos,int val)
{
    if(x[pos]>1) s.erase(pos);
    x[pos]=val;
    if(x[pos]>1) s.insert(pos);
    update(1,0,n-1,pos,x[pos],0);
    return solve();
}

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

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