제출 #1277525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277525		k12_khoi	말 (IOI15_horses)	C++17	100 / 100	642 ms	46000 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 = 500000 + 5;
const int mod = 1000000007;
const int limit = 1000000000;

int n, request, type, x, y, u, v, k;
int a[N], b[N], Xarr[N], Yarr[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);
}

// build using pref_mod to avoid side effects of modifying cur inside recursion
function<void(int,int,int, const vector<int>&)> build; // forward

int init(int nn, int aarr[], int barr[]) {
    ::n = nn;
    for (int i = 0; i < n; ++i) {
        Xarr[i] = aarr[i];
        Yarr[i] = barr[i];
    }

    // prepare prefix modulo array (prefix_mod[i] = X[0]*...*X[i-1] mod)
    vector<int> prefix_mod(n + 1);
    prefix_mod[0] = 1;
    for (int i = 1; i <= n; ++i) prefix_mod[i] = mul(prefix_mod[i - 1], Xarr[i - 1]);

    long long cur=1;

    // build function (uses prefix_mod)
    build = [&](int id, int l, int r, const vector<int> &pref_mod) {
        lazy[id] = 1;
        tTwo[id] = 1;
        if (l == r) {
            if (l == 0) t[id] = 1;
            else t[id] = Yarr[l - 1],cur=mul(cur,Xarr[l-1]);
            tTwo[id] = cur; // prefix mod for leaf l
            return;
        }
        int m = (l + r) >> 1;
        build(id << 1, l, m, pref_mod);
        build(id << 1 | 1, m + 1, r, pref_mod);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    };

    // build tree
    build(1, 0, n, prefix_mod);

    // fill set se
    se.insert(0);
    for (int i = 0; i < n; ++i) if (Xarr[i] != 1) se.insert(i + 1);

    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*=Xarr[(*it)-1];
        if (cur>=limit) break;

        it--;

        u=*it;
        v=n;
        int 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 (Xarr[pos-1]!=val)
    {
        if (Xarr[pos-1]==1) se.insert(pos);

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

        Xarr[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())
    {
        if (*it) cur*=Xarr[(*it)-1];
        if (cur>=limit) break;

        it--;

        u=*it;
        v=n;
        int 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 (Yarr[pos-1]!=val)
    {
        u=pos;
        k=val;
        update_point(1,0,n);

        Yarr[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*=Xarr[(*it)-1];
        if (cur>=limit) break;

        it--;

        u=*it;
        v=n;
        int 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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23