Submission #87755

#	Time	Username	Problem	Language	Result	Execution time	Memory
87755		JustasZ	Horses (IOI15_horses)	C++14	100 / 100	551 ms	121884 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) "["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=5e5+100;
const int mod=1e9+7;
const ld eps=1e-5;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll pwr(ll a, ll pw)
{
    ll ret=1;
    while(pw>0)
    {
        if(pw&1)ret=ret*a%mod;
        a=a*a%mod;
        pw>>=1;
    }
    return ret;
}
ll modinv(ll a)
{
    return pwr(a, mod-2);
}
int N;
ll X[maxn], Y[maxn], prod[maxn];
ld Xpref[maxn];
pair<ld, ll> seg[maxn*4], lazy[maxn*4];
bool need[maxn*4];
void build(int id=1, int l=0, int r=N-1)
{
    if(l == r)
    {
        seg[id].x=Xpref[l]+log((ld)Y[l]);
        seg[id].y=prod[l]*Y[l]%mod;
        return;
    }
    int mid=(l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    seg[id]=max(seg[id*2], seg[id*2+1]);
}
void laz(int id, ld d, ll mul)
{
    seg[id].x+=d;
    lazy[id].x+=d;
    seg[id].y=seg[id].y*mul%mod;
    lazy[id].y=lazy[id].y*mul%mod;
    need[id]=true;
}
void shift(int id)
{
    if(need[id])
    {
        laz(id*2, lazy[id].x, lazy[id].y);
        laz(id*2+1, lazy[id].x, lazy[id].y);
        need[id]=false;
        lazy[id]={0, 1};
    }
}
void modify(int x, int y, ld d, ll mul, int id=1, int l=0, int r=N-1)
{
    if(l > y || r < x)return;
    if(l >= x && r <= y)
    {
        laz(id, d, mul);
        return;
    }
    shift(id);
    int mid=(l+r)/2;
    modify(x, y, d, mul, id*2, l, mid);
    modify(x, y, d, mul, id*2+1, mid+1, r);
    seg[id]=max(seg[id*2], seg[id*2+1]);
}
pair<ld, ll> query(int x, int y, int id=1, int l=0, int r=N-1)
{
    if(l > y || r < x)return {0, 0};
    if(l >= x && r <= y)return seg[id];
    shift(id);
    int mid=(l+r)/2;
    return max(query(x, y, id*2, l, mid), query(x, y, id*2+1, mid+1, r));
}
int getans()
{
    return (int)(query(0, N-1).y);
}
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];
    for(int i=0; i<N; i++)
    {
        Xpref[i]=log((ld)X[i]);
        prod[i]=X[i];
        if(i > 0)Xpref[i]+=Xpref[i-1];
        if(i > 0)prod[i]=prod[i]*prod[i-1]%mod;
    }
    for(int i=0; i<maxn*4; i++)lazy[i].y=1;
    build();
    return getans();
}
int updateX(int p, int val)
{
    ld d=log((ld)val)-log((ld)X[p]);
    ll mul=modinv(X[p])*(ll)val%mod;
    X[p]=val;
    modify(p, N-1, d, mul);
    return getans();
}
int updateY(int p, int val)
{
    ld d=log((ld)val)-log((ld)Y[p]);
    ll mul=modinv(Y[p])*(ll)val%mod;
    Y[p]=val;
    modify(p, p, d, mul);
    return getans();
}

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