Submission #259347

#	Time	Username	Problem	Language	Result	Execution time	Memory
259347		IOrtroiii	Horses (IOI15_horses)	C++14	100 / 100	344 ms	75000 KiB

horses

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int MX = 1 << 19;

int N;
int X[MX], Y[MX];

pair<ld, int> best[MX << 2];
ld sum[MX << 2];

void pop(int v) {
   best[v] = max(best[v << 1], make_pair(best[v << 1 | 1].first + sum[v << 1], best[v << 1 | 1].second));
   sum[v] = sum[v << 1] + sum[v << 1 | 1];
}

void init(int v, int l, int r) {
   if (l == r) {
      best[v] = make_pair(log(X[l]) + log(Y[l]), l);
      sum[v] = log(X[l]);
      return;
   }
   int md = (l + r) >> 1;
   init(v << 1, l, md);
   init(v << 1 | 1, md + 1, r);
   pop(v);
}

void modify(int v, int l, int r, int p) {
   if (l == r) {
      best[v] = make_pair(log(X[l]) + log(Y[l]), l);
      sum[v] = log(X[l]);
      return;
   }
   int md = (l + r) >> 1;
   if (p <= md) modify(v << 1, l, md, p);
   else modify(v << 1 | 1, md + 1, r, p);
   pop(v);
}

const int MOD = 1000000007;

int mult(int x, int y) { return ll(x) * y % MOD; }
int st[MX << 2];

int _N;

void init() {
   _N = 1;
   while (_N < N) _N <<= 1;
   for (int i = 0; i < N; ++i) {
      st[_N + i] = X[i];
   }
   for (int i = _N - 1; i >= 1; --i) st[i] = mult(st[i << 1], st[i << 1 | 1]);
}

void modify(int p) {
   st[p + _N] = X[p];
   p += _N;
   for (p >>= 1; p > 0; p >>= 1) {
      st[p] = mult(st[p << 1], st[p << 1 | 1]);
   }
}

int query(int p) {
   int ans = Y[p];
   for (int l = _N, r = p + _N; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) ans = mult(ans, st[l++]);
      if (!(r & 1)) ans = mult(ans, st[r--]);
   }
   return ans;
}

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];
   init(1, 0, N - 1);
   init();
   return query(best[1].second);
}

int updateX(int pos, int val) {
   X[pos] = val;
   modify(1, 0, N - 1, pos);
   modify(pos);
   return query(best[1].second);
}

int updateY(int pos, int val) {
   Y[pos] = val;
   modify(1, 0, N - 1, pos);
   modify(pos);
   return query(best[1].second);
}

Compilation message (stderr)

horses.cpp: In function 'int mult(int, int)':
horses.cpp:47:43: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
 int mult(int x, int y) { return ll(x) * y % MOD; }
                                 ~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:78:36: warning: declaration of '_N' shadows a global declaration [-Wshadow]
 int init(int _N, int _X[], int _Y[]) {
                                    ^
horses.cpp:50:5: note: shadowed declaration is here
 int _N;
     ^~

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