Submission #1313514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313514		activedeltorre	말 (IOI15_horses)	C++20	100 / 100	802 ms	82376 KiB

horses

#include "horses.h"
#include<iostream>
#include<cmath>
using namespace std;
int n;
int x[500005];
long double v1[500005];
long double v2[500005];
long double ainty[2000005];
long double lazy[2000005];
long double posy[2000005];
long long prod[2000005];
long long mod=1e9+7;
void build(int node,int st,int dr)
{
    lazy[node]=0;
    ainty[node]=0;
    if(st==dr)
    {
        posy[node]=st;
        ainty[node]=v2[st];
        prod[node]=x[st];
        return ;
    }
    int mij=(st+dr)/2;
    build(node*2,st,mij);
    build(node*2+1,mij+1,dr);
    posy[node]=posy[node*2];
    prod[node]=(1ll*prod[node*2]*prod[node*2+1])%mod;
}
void push(int node,int st,int dr)
{
    ainty[node]+=lazy[node];
    if(st!=dr)
    {
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
}
void updatey(int node,int st,int dr,int qst,int qdr,long double val)
{
    push(node,st,dr);
    if(st>dr || st>qdr || qst>dr || qst>qdr)
    {
        return ;
    }
    if(qst<=st && dr<=qdr)
    {
        lazy[node]=val;
        push(node,st,dr);
        return;
    }
    int mij=(st+dr)/2;
    updatey(node*2,st,mij,qst,qdr,val);
    updatey(node*2+1,mij+1,dr,qst,qdr,val);
    ainty[node]=max(ainty[node*2],ainty[node*2+1]);
    if(ainty[node]==ainty[node*2])
    {
        posy[node]=posy[node*2];
    }
    else
    {
        posy[node]=posy[node*2+1];
    }
}
void updatex(int node,int st,int dr,int pos,long double val)
{
    if(st>pos || pos>dr)
    {
        return ;
    }
    if(st==dr)
    {
        prod[node]=val;
        return;
    }
    int mij=(st+dr)/2;
    updatex(node*2,st,mij,pos,val);
    updatex(node*2+1,mij+1,dr,pos,val);
    prod[node]=(1ll*prod[node*2]*prod[node*2+1])%mod;
}
long long query(int node,int st,int dr,int qst,long double qdr)
{
    if(st>dr || st>qdr || qst>dr || qst>qdr)
    {
        return 1;
    }
    if(qst<=st && dr<=qdr)
    {
        return prod[node];
    }
    int mij=(st+dr)/2;
    long long r1,r2;
    r1=query(node*2,st,mij,qst,qdr);
    r2=query(node*2+1,mij+1,dr,qst,qdr);
    return (1ll*r1*r2)%mod;
}
int y[500005];
long long eval()
{
    int pos=posy[1];
    return (y[pos]*query(1,0,n-1,0,pos))%mod;
}
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];
        v1[i]=log((long double)x[i]);
        v2[i]=log((long double)y[i]);
    }
    build(1,0,n-1);
    for(int i=0;i<n;i++)
    {
        updatey(1,0,n-1,i,n-1,v1[i]);
    }
	return eval();
}
int updateX(int pos, int val) {
    long double diff=v1[pos];
    x[pos]=val;
    v1[pos]=log((long double)x[pos]);
    updatey(1,0,n-1,pos,n-1,v1[pos]-diff);
    updatex(1,0,n-1,pos,x[pos]);
	return eval();
}

int updateY(int pos, int val) {
    long double diff=v2[pos];
    y[pos]=val;
    v2[pos]=log((long double)y[pos]);
    updatey(1,0,n-1,pos,pos,v2[pos]-diff);
	return eval();
}

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