Submission #308460

#	Time	Username	Problem	Language	Result	Execution time	Memory
308460		quocnguyen1012	Horses (IOI15_horses)	C++14	0 / 100	108 ms	50000 KiB

horses

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e5 + 5, mod = 1e9 + 7;

struct Node {
  ll a, b;
  double la, lb;
};

Node operator + (const Node & l, const Node & r) {
  Node res;
  res.a = l.a * l.b % mod;
  res.la = l.la + r.la;
  if (l.lb > l.la + r.lb) {
    res.lb = l.lb;
    res.b = l.b;
  } else {
    res.lb = l.la + r.lb;
    res.b = l.a * r.b % mod;
  }
  return res;
}

Node tr[4 * maxn];
vector<ll> x, y;
int N;

void apply(int id, int l) {
  tr[id].a = x[l];
  tr[id].b = x[l] * y[l] % mod;
  tr[id].la = log2(x[l]);
  tr[id].lb = log2(y[l]) + log2(x[l]);
}

#define lc id << 1
#define rc id << 1 | 1
void build(int id, int l, int r) {
  if (l == r) {
    apply(id, l);
    return;
  }
  int mid = (l + r) / 2;
  build(lc, l, mid); build(rc, mid + 1, r);
  tr[id] = tr[lc] + tr[rc];
}

void upd(int type, int pos, ll v, int id = 1, int l = 0, int r = N - 1) {
  if (l == r) {
    if (type == 0) x[l] = v;
    else y[l] = v;
    apply(id, pos);
    return;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) upd(type, pos, v, lc, l, mid);
  else upd(type, pos, v, rc, mid + 1, r);
  tr[id] = tr[lc] + tr[rc];
}

#undef lc
#undef rc
int init(int _N, int X[], int Y[]) {
	N = _N;
  for (int i = 0; i < N; ++i) {
    x.eb(X[i]);
    y.eb(Y[i]);
  }
  build(1, 0, N - 1);
	return tr[1].b;
}

int updateX(int pos, int val) {
	upd(0, pos, val);
	return tr[1].b;
}

int updateY(int pos, int val) {
	upd(1, pos, val);
	return tr[1].b;
}

#ifdef LOCAL
signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL

  int N;
  cin >> N;
  int X[N], Y[N];
  for(int i = 0; i < N; i++) cin >> X[i];
  for(int i = 0; i < N; i++) cin >> Y[i];
  cout << init(N, X, Y);
}
#endif // LOCAL

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |  return tr[1].b;
      |         ~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:86:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   86 |  return tr[1].b;
      |         ~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |  return tr[1].b;
      |         ~~~~~~^

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