Submission #1147024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147024		alexdd	Horses (IOI15_horses)	C++20	17 / 100	517 ms	40788 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
const ll INF = 1e9;
int n;
set<int> s;

int aint[1100000];
void upd(int nod, int st, int dr, int poz, int newv)
{
    if(st==dr)
    {
        aint[nod] = newv;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return 0;
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return max(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}

ll put(ll a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put(a*a%MOD,exp/2);
    else
        return put(a*a%MOD,exp/2)*a%MOD;
}

ll X[500005],Y[500005];
ll tot;
long long solve()
{
    s.insert(0);
    auto it = s.end();
    vector<int> pozs;
    ll prod=1;
    while(it!=s.begin() && prod<INF)
    {
        it--;
        //if(prod * X[*it] > INF) break;
        pozs.push_back(*it);
        prod *= X[pozs.back()];
    }
    reverse(pozs.begin(),pozs.end());
    ll pref=1;
    ll mxm=0;
    for(int i:pozs)
    {
        pref *= X[i];
        mxm = max(mxm, pref * qry(1,0,n-1,i,n-1));
    }
    return mxm * tot%MOD * put(prod,MOD-2)%MOD;
}

int init(int N, int copX[], int copY[])
{
    for(int i=0;i<N;i++)
    {
        X[i] = copX[i];
        Y[i] = copY[i];
    }
    n=N;
    tot=1;
    for(int i=0;i<N;i++)
    {
        if(X[i]>1) s.insert(i);
        upd(1,0,n-1,i,Y[i]);
        tot = tot*X[i]%MOD;
    }
    return solve();
}

int updateX(int pos, int val)
{
    tot = tot * put(X[pos],MOD-2)%MOD * val%MOD;
    X[pos] = val;
    s.erase(pos);
    if(val>1) s.insert(pos);
    return solve();
}

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

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