제출 #1276862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276862		k12_khoi	말 (IOI15_horses)	C++17	17 / 100	140 ms	44036 KiB

horses

#include "horses.h"

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

#define ll long long
#define pii pair<ll,ll>
#define X first
#define Y second

const int N=5e5+5;
const int mod=1e9+7;
const int limit=1e9;

int n,request,type,x,y,u,v,k;
int a[N],b[N],X[N],Y[N],t[4*N],lazy[4*N],tTwo[4*N];
set <int> se;
set <int> :: iterator it;

int mul(int x,int y)
{
    return 1LL*x*y%mod;
}

int luythua(int x,int n)
{
    int c=1;
    while (n)
    {
        if (n&1) c=mul(c,x);
        x=mul(x,x);

        n/=2;
    }

    return c;
}

void down(int id)
{
    if (lazy[id]!=1)
    {
        lazy[id*2]=mul(lazy[id*2],lazy[id]);
        lazy[id*2+1]=mul(lazy[id*2+1],lazy[id]);

        tTwo[id*2]=mul(tTwo[id*2],lazy[id]);
        tTwo[id*2+1]=mul(tTwo[id*2+1],lazy[id]);

        lazy[id]=1;
    }
}

void update_range(int id,int l,int r)
{
    if (u>r or v<l) return;
    if (u<=l and v>=r)
    {
        tTwo[id]=mul(tTwo[id],k);
        lazy[id]=mul(lazy[id],k);

        return;
    }
    down(id);
    int m=(l+r)/2;
    update_range(id*2,l,m);
    update_range(id*2+1,m+1,r);
}

void update_point(int id,int l,int r)
{
    if (l==r)
    {
        t[id]=k;
        return;
    }
    int m=(l+r)/2;
    if (u<=m) update_point(id*2,l,m);
    else update_point(id*2+1,m+1,r);
    t[id]=max(t[id*2],t[id*2+1]);
}

int get_range(int id,int l,int r)
{
    if (u>r or v<l) return 0;
    if (u<=l and v>=r) return t[id];
    int m=(l+r)/2;

    return max(get_range(id*2,l,m),get_range(id*2+1,m+1,r));
}

ll get_point(int id,int l,int r)
{
    if (l==r)
        return tTwo[id];

    down(id);
    int m=(l+r)/2;

    if (u<=m) return get_point(id*2,l,m);
    else return get_point(id*2+1,m+1,r);
}

int init(int n,int a[],int b[])
{
    for (int i=0;i<n;i++)
    {
        X[i]=a[i];
        Y[i]=b[i];
    }

    ll cur=1;

    function <void(int,int,int)> build = [&] (int id,int l,int r) -> void
    {
        lazy[id]=1;
        tTwo[id]=1;

        if (l==r)
        {
            if (l==0) t[id]=1;
            else t[id]=Y[l-1];

            if (l) cur=mul(cur,X[l-1]);
            tTwo[id]=cur;

            return;
        }
        int m=(l+r)/2;
        build(id*2,l,m);
        build(id*2+1,m+1,r);
        t[id]=max(t[id*2],t[id*2+1]);
    };


    se.insert(0);
    for (int i=0;i<n;i++)
    if (X[i]!=1) se.insert(i+1);


    build(1,0,n);


    it=--se.end();

    u=*it;
    v=n;
    pii ma=make_pair(get_range(1,0,n),1);
    ll temp;
    int best=*it;
    cur=1;
    while (it!=se.begin())
    {
        if (*it) cur*=X[(*it)-1];
        if (cur>=limit) break;

        it--;

        u=*it;
        v=n;
        temp=get_range(1,0,n);
        if (ma.X*cur<temp*ma.Y)
        {
            best=*it;
            cur=1;
            ma=make_pair(temp,cur);
        }
    }

    u=best;
    temp=get_point(1,0,n);

    u=best;
    v=n;

    return mul(temp,get_range(1,0,n));
}

int updateX(int pos,int val)
{
    pos++;

    if (X[pos-1]!=val)
    {
        if (X[pos-1]==1) se.insert(pos);

        k=mul(luythua(X[pos-1],mod-2),val);
        u=pos;
        v=n;
        update_range(1,0,n);

        X[pos-1]=val;

        if (val==1) se.erase(pos);
    }


    it=--se.end();

    u=*it;
    v=n;
    pii ma=make_pair(get_range(1,0,n),1);
    ll temp;
    int best=*it;
    ll cur=1;
    while (it!=se.begin())
    {
        cur*=X[(*it)-1];
        if (cur>=limit) break;

        it--;


        u=*it;
        v=n;
        temp=get_range(1,0,n);

        if (ma.X*cur<temp*ma.Y)
        {
            best=*it;
            cur=1;
            ma=make_pair(temp,cur);
        }
    }

    u=best;
    temp=get_point(1,0,n);

    u=best;
    v=n;

    return mul(temp,get_range(1,0,n));
}

int updateY(int pos,int val)
{
    pos++;

    if (Y[pos-1]!=val)
    {
        u=pos;
        k=val;
        update_point(1,0,n);

        Y[pos-1]=val;
    }


    it=--se.end();

    u=*it;
    v=n;
    pii ma=make_pair(get_range(1,0,n),1);
    ll temp;
    int best=*it;
    ll cur=1;
    while (it!=se.begin())
    {
        if (*it) cur*=X[(*it)-1];
        if (cur>=limit) break;

        it--;

        u=*it;
        v=n;
        temp=get_range(1,0,n);
        if (ma.X*cur<temp*ma.Y)
        {
            best=*it;
            cur=1;
            ma=make_pair(temp,cur);
        }
    }

    u=best;
    temp=get_point(1,0,n);

    u=best;
    v=n;

    return mul(temp,get_range(1,0,n));
}

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