Submission #521352

#	Time	Username	Problem	Language	Result	Execution time	Memory
521352		Alex_tz307	Horses (IOI15_horses)	C++17	100 / 100	268 ms	59192 KiB

horses

#include <bits/stdc++.h>

using namespace std;
using ld = long double;

const int mod = 1e9 + 7;

void addSelf(int &x, const int &y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int add(int x, const int &y) {
  addSelf(x, y);
  return x;
}

void multSelf(int &x, const int &y) {
  x = (int64_t)x * y % mod;
}

int mult(int x, const int &y) {
  multSelf(x, y);
  return x;
}

int Pow(int x, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) {
      multSelf(ans, x);
    }
    multSelf(x, x);
    n >>= 1;
  }
  return ans;
}

int invers(int x) {
  return Pow(x, mod - 2);
}

struct node {
  ld maxSum, lazySum;
  int maxProd, lazyProd;

  node operator + (const node &rhs) const {
    node ret;
    ret.maxSum = max(maxSum, rhs.maxSum);
    if (maxSum == ret.maxSum) {
      ret.maxProd = maxProd;
    } else {
      ret.maxProd = rhs.maxProd;
    }
    ret.lazySum = 0;
    ret.lazyProd = 1;
    return ret;
  };
};

const int kN = 5e5;
int n, Prod = 1, A[1 + kN], B[1 + kN];
ld Sum;

struct ST {
  vector<node> t;

  void init() {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      Sum += log(A[lx]);
      multSelf(Prod, A[lx]);
      t[x] = {Sum + log(B[lx]), 0, mult(Prod, B[lx]), 1};
      return;
    }
    int mid = (lx + rx) / 2;
    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void updateNode(int x, ld lazySum, int lazyProd) {
    t[x].maxSum += lazySum;
    t[x].lazySum += lazySum;
    multSelf(t[x].maxProd, lazyProd);
    multSelf(t[x].lazyProd, lazyProd);
  }

  void push(int x) {
    for (int i = 0; i < 2; ++i) {
      updateNode(x * 2 + i, t[x].lazySum, t[x].lazyProd);
    }
    t[x].lazySum = 0;
    t[x].lazyProd = 1;
  }

  void update(int x, int lx, int rx, int st, int dr, ld lazySum, int lazyProd) {
    if (st <= lx && rx <= dr) {
      updateNode(x, lazySum, lazyProd);
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      update(x * 2, lx, mid, st, dr, lazySum, lazyProd);
    }
    if (mid < dr) {
      update(x * 2 + 1, mid + 1, rx, st, dr, lazySum, lazyProd);
    }
    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void update(int st, int dr, ld lazySum, int lazyProd) {
    update(1, 1, n, st, dr, lazySum, lazyProd);
  }
} t;

int init(int N, int X[], int Y[]) {
  n = N;
  for (int i = 1; i <= n; ++i) {
    A[i] = X[i - 1];
    B[i] = Y[i - 1];
  }
  t.init();
  t.build(1, 1, n);
  return t.t[1].maxProd;
}

int updateX(int pos, int val) {
  pos += 1;
  t.update(pos, n, log(val) - log(A[pos]), mult(invers(A[pos]), val));
  A[pos] = val;
  return t.t[1].maxProd;
}

int updateY(int pos, int val) {
  pos += 1;
  t.update(pos, pos, log(val) - log(B[pos]), mult(invers(B[pos]), val));
  B[pos] = val;
  return t.t[1].maxProd;
}

Compilation message (stderr)

horses.cpp: In function 'void multSelf(int&, const int&)':
horses.cpp:21:22: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
   21 |   x = (int64_t)x * y % mod;
      |       ~~~~~~~~~~~~~~~^~~~~

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