Submission #1223114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223114		kunzaZa183	Horses (IOI15_horses)	C++20	34 / 100	1598 ms	47980 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
const int mn = 5e5;
int maxy[4 * mn];
void umy(int curin, int curl, int curr, int in, int val) {
  if (curl == curr) {
    maxy[curin] = val;
    return;
  }
  int mid = (curl + curr) / 2;
  if (in <= mid)
    umy(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
  else
    umy(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
  maxy[curin] = max(maxy[curin * 2 + 1], maxy[curin * 2 + 2]);
}
int qmy(int curin, int curl, int curr, int ql, int qr) {
  if (curl > qr || curr < ql)
    return -1;
  if (curl == curr) {
    return maxy[curin];
  }
  return max(qmy(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
             qmy(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}

ll totval[4 * mn];
void utl(int curin, int curl, int curr, int in, int val) {
  if (curl == curr) {
    totval[curin] = val;
    return;
  }
  int mid = (curl + curr) / 2;
  if (in <= mid)
    utl(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
  else
    utl(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
  totval[curin] = totval[curin * 2 + 1] * totval[curin * 2 + 2] % MOD;
}
ll qtl(int curin, int curl, int curr, int ql, int qr) {
  if (ql > curr || qr < curl)
    return 1;
  if (curl == curr) {
    return totval[curin];
  }
  ll a = qtl(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
     b = qtl(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr);
  return a * b % MOD;
}

int n;
vector<ll> x, y;
set<int, greater<int>> sigi;

int ans() {
  sigi.insert(0);
  if (sigi.empty())
    return qmy(0, 0, n - 1, 0, n - 1);
  // cout << "X: ";
  // for (int i = 0; i < n; i++) {
  //   cout << x[i] << ' ';
  // }
  // cout << "\n";
  //
  // cout << "Y: ";
  // for (int i = 0; i < n; i++) {
  //   cout << y[i] << ' ';
  // }
  // cout << "\n";

  ll maxyval = qmy(0, 0, n - 1, *sigi.begin(), n - 1);
  int maxin = *sigi.begin();

  // cout << "FIRSTMAXIN = " << maxin << "\n";

  auto it = sigi.begin();
  int prev = *it;
  ll diff = x[*it];
  int ct = 0;
  for (++it; it != sigi.end(); it++) {
    int yval = qmy(0, 0, n - 1, *it, prev - 1);
    ct++;
    assert(ct <= 35);
    // cout << *it << " " << prev << '\n';
    // cout << "Curin " << curin << " " << maxin << "\n";
    // cout << "Diff = " << diff << "\n";

    if (diff * maxyval >= MOD)
      return qtl(0, 0, n - 1, 0, maxin) * maxyval % MOD;

    if (diff * maxyval < yval) {
      maxyval = yval;
      maxin = *it;
      diff = 1;
    }

    diff *= x[*it];

    prev = *it;
  }

  // cout << "MAXIN = " << maxin << "\n";

  return qtl(0, 0, n - 1, 0, maxin) * maxyval % MOD;
}

int init(int N, int X[], int Y[]) {
  n = N;
  y = x = vector<ll>(n);
  for (int i = 0; i < n; i++) {
    umy(0, 0, n - 1, i, Y[i]);
    utl(0, 0, n - 1, i, X[i]);
    x[i] = X[i], y[i] = Y[i];
  }

  for (int i = 0; i < n; i++)
    if (X[i] >= 2)
      sigi.insert(i);

  return ans();
}

int updateX(int pos, int val) {
  utl(0, 0, n - 1, pos, val);
  int orig = x[pos];
  x[pos] = val;
  if ((orig >= 2) == (val >= 2))
    return ans();
  if (orig >= 2)
    sigi.erase(pos);
  else
    sigi.insert(pos);

  return ans();
}

int updateY(int pos, int val) {
  umy(0, 0, n - 1, pos, val);
  y[pos] = val;
  return ans();
}

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