제출 #1193052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193052		vivkostov	Horses (IOI15_horses)	C++20	17 / 100	1593 ms	24828 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e9+7;
int br[2000005],ma[2000005],n,a[500005],b[500005];
long long int p[2000005];
vector<int>pos;
void build(int l,int r,int h)
{
    if(l==r)
    {
        p[h]=a[l];
        if(b[l]!=1)br[h]=1;
        ma[h]=b[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,h*2);
    build(mid+1,r,h*2+1);
    p[h]=(p[h*2]*p[h*2+1])%maxn;
    br[h]=br[h*2]+br[h*2+1];
    ma[h]=max(ma[h*2],ma[h*2+1]);
}
void updateA(int l,int r,int q,int h,int st)
{
    if(l>q||r<q)return;
    if(l==r)
    {
        a[l]=st;
        p[h]=a[l];
        return;
    }
    int mid=(l+r)/2;
    updateA(l,mid,q,h*2,st);
    updateA(mid+1,r,q,h*2+1,st);
    p[h]=(p[h*2]*p[h*2+1])%maxn;
}
void updateB(int l,int r,int q,int h,int st)
{
    if(l>q||r<q)return;
    if(l==r)
    {
        b[l]=st;
        if(b[l]!=1)br[h]=1;
        else br[h]=0;
        ma[h]=st;
        return;
    }
    int mid=(l+r)/2;
    updateB(l,mid,q,h*2,st);
    updateB(mid+1,r,q,h*2+1,st);
    br[h]=br[h*2]+br[h*2+1];
    ma[h]=max(ma[h*2],ma[h*2+1]);
}
void get_pos(int l,int r,int q,int h)
{
    if(l==r)
    {
        pos.push_back(l);
        return;
    }
    int mid=(l+r)/2;
    if(br[h*2+1]<q)
    {
        get_pos(l,mid,q-br[h*2+1],h*2);
    }
    get_pos(mid+1,r,q,h*2+1);
}
long long int get_um(int l,int r,int ql,int qr,int h)
{
    if(l>qr||r<ql)return 1;
    if(l>=ql&&r<=qr)return p[h];
    int mid=(l+r)/2;
    return (get_um(l,mid,ql,qr,h*2)*get_um(mid+1,r,ql,qr,h*2+1))%maxn;
}
int get_ma(int l,int r,int ql,int qr,int h)
{
    if(l>qr||r<ql)return 0;
    if(l>=ql&&r<=qr)return ma[h];
    int mid=(l+r)/2;
    return max(get_ma(l,mid,ql,qr,h*2),get_ma(mid+1,r,ql,qr,h*2+1));
}
void check(int l,int r,int h)
{
    cout<<l<<" "<<r<<" "<<p[h]<<" "<<br[h]<<" "<<ma[h]<<endl;
    if(l==r)return;
    int mid=(l+r)/2;
    check(l,mid,h*2);
    check(mid+1,r,h*2+1);
}
int resh()
{
    get_pos(1,n,30,1);
    pos.push_back(n+1);
    long long int otg=0,cur;
    for(int i=0;i<pos.size()-1;i++)
    {
        cur=get_um(1,n,1,pos[i],1);
        cur*=get_ma(1,n,pos[i],pos[i+1]-1,1);
        otg=max(otg,cur);
        cur=0;
    }
    pos.clear();
    return otg;
}
int init(int N, int X[], int Y[])
{
    n=N;
    for(int i=0;i<n;i++)
    {
        a[i+1]=X[i];
        b[i+1]=Y[i];
    }
    build(1,n,1);
	return resh();
}

int updateX(int po, int val)
{
    po++;
    updateA(1,n,po,1,val);
	return resh();
}

int updateY(int po, int val)
{
    po++;
    updateB(1,n,po,1,val);
	return resh();
}

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