Submission #1193045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193045		vivkostov	Horses (IOI15_horses)	C++20	0 / 100	41 ms	22596 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];
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 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 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 0;
}

int updateX(int pos, int val)
{
    pos++;
    updateA(1,n,pos,1,val);
	return 0;
}

int updateY(int pos, int val)
{
    pos++;
    updateB(1,n,pos,1,val);
	return 0;
}

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