Submission #1197737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197737		abdelhakim	Horses (IOI15_horses)	C++20	17 / 100	41 ms	28744 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define mod (ll)(1e9+7)
#define inf (ll)(1e18)
#define dbg(x) cerr << #x<< ' '<<x << endl;
ll maxn = 5e5;
vector<ll> tree(4*maxn+7,1);
ll n=0;
vector<ll> x;
vector<ll> y; 
void update(ll node, ll l, ll r, ll pos, ll val)
{
    if(r<l)return;
    if(pos < l || pos > r)
    {
        return;
    }
    if(l==r)
    {
        tree[node]=val;return;
    }
    ll mid=(l+r)/2;
    update(node*2+1,l,mid,pos,val);
    update(node*2+2,mid+1,r,pos,val);
    tree[node]=tree[node*2+1]*tree[node*2+2]%mod;
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
    if(max(l,x)>min(r,y))
    {
        return 1;
    }
    if(x<=l && r<=y)
    {
        return tree[node];
    }
    ll mid=(l+r)/2;
    return query(node*2+1,l,mid,x,y)%mod*query(node*2+2,mid+1,r,x,y)%mod;
}
int init(int N, int X[], int Y[])
{
    x.resize(N);
    y.resize(N);
    for (int i = 0;i<N;i++)
    {
        x[i]=X[i];
        y[i]=Y[i];
    }
    n=N;
    ll ans=0;
    ll cur=1;
    for (int i = max(0,N-30);i<N;i++)
    {
        cur*=x[i];
        ans=max(ans,y[i]*cur);
    }
    ans%=mod;
    ll cur2 = query(0,0,n-1,0,max(0,N-31));
    cur2%=mod;
    int lst = ans%mod*(cur2%mod)%mod;
    return lst;
}
int updateX(int ops, int val)
{
    x[ops]=val;
    update(0,0,n-1,ops,x[ops]);
    ll ans=0;
    ll cur=1;
    for (int i = max(0,(int)n-30);i<n;i++)
    {
        cur*=x[i];
        ans=max(ans,y[i]*cur);
    }
    ans%=mod;
    ll cur2 = query(0,0,n-1,0,max(0,(int)n-31));
    cur2%=mod;
    int lst = ans%mod*(cur2%mod)%mod;
    return lst;
}

int updateY(int ops, int val)
{
    y[ops]=val;
    ll ans=0;
    ll cur=1;
    for (int i = max(0,(int)n-30);i<n;i++)
    {
        cur*=x[i];
        ans=max(ans,y[i]*cur);
    }
    ans%=mod;
    ll cur2 = query(0,0,n-1,0,max(0,(int)n-31));
    cur2%=mod;
    int lst = ans%mod*(cur2%mod)%mod;
    return lst;
}

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