Submission #1189075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189075		raspy	Horses (IOI15_horses)	C++20	17 / 100	174 ms	45952 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MAX_N = 5e5+5;
const int mod = 1e9+7;

struct node
{
  ll x_pr;
  ll rez;
  double lgpr;
  double lgrez;
};

ll n;
ll x[MAX_N], y[MAX_N];
node seg[MAX_N*4];

void upd(int v, int l, int r, int ix, pair<int, int> a)
{
  if (l > r) return;
  if (l==r)
  {
    seg[v].x_pr = a.first;
    seg[v].rez = a.first*a.second%mod;
    seg[v].lgpr = log((double)a.first);
    seg[v].lgrez = log((double)(a.second*a.first));
    return;
  }
  int mid = (l+r) / 2;
  if (ix <= mid)
    upd(v*2+1, l, mid, ix, a);
  else
    upd(v*2+2, mid+1, r, ix, a);
  int lv = v*2+1, ds = v*2+2;
  seg[v].x_pr = seg[lv].x_pr*seg[ds].x_pr%mod;
  seg[v].lgpr = seg[lv].lgpr+seg[ds].lgpr;
  if (seg[lv].lgpr + seg[ds].lgrez >= seg[lv].lgrez)
  {
    seg[v].lgrez = seg[lv].lgpr + seg[ds].lgrez;
    seg[v].rez = seg[lv].x_pr*seg[ds].rez%mod;
  }
  else
  {
    seg[v].lgrez = seg[lv].lgrez;
    seg[v].rez = seg[lv].rez;
  }
}

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];
    upd(0, 0, n-1, i, {x[i], y[i]});
  }
  return seg[0].rez;
}

int updateX(int pos, int val)
{
  x[pos] = val;
  upd(0, 0, n-1, pos, {x[pos], y[pos]});
  return seg[0].rez;
}

int updateY(int pos, int val)
{
  y[pos] = val;
  upd(0, 0, n-1, pos, {x[pos], y[pos]});
  return seg[0].rez;
}

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