Submission #708592

#	Time	Username	Problem	Language	Result	Execution time	Memory
708592		cig32	Horses (IOI15_horses)	C++17	100 / 100	669 ms	123444 KiB

horses

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 14;
const int MOD = 1e9 + 7;
long long x[MAXN];
long long y[MAXN];
int n;


struct segtr {
  long double ans = 0, lazy = 0;
  bool push = 0;
  int id;
} st[4 * MAXN];

void push_down(int idx) {
  if(st[idx].push) {
    st[2*idx+1].ans += st[idx].lazy;
    st[2*idx+1].lazy += st[idx].lazy;
    st[2*idx+1].push = 1;
    st[2*idx+2].ans += st[idx].lazy;
    st[2*idx+2].lazy += st[idx].lazy;
    st[2*idx+2].push = 1;
    st[idx].push = 0;
    st[idx].lazy = 0;
  }
}

void build(int l, int r, int tar) {
  if(l == r) {
    st[tar].id = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2*tar + 1);
  build(mid+1, r, 2*tar + 2);
  st[tar].id = st[2*tar+1].id;
}
void u(int l, int r, int constl, int constr, int idx, long double uwu) {

  if(l <= constl && constr <= r) {
    st[idx].ans += uwu;
    st[idx].lazy += uwu;
    st[idx].push = 1;
    return;
  }
  push_down(idx);
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) u(l, r, mid + 1, constr, 2 * idx + 2, uwu);
  else if(constr < l || r < mid+1) u(l, r, constl, mid, 2 * idx + 1, uwu);
  else {
    u(l, r, constl, mid, 2 * idx + 1, uwu);
    u(l, r, mid + 1, constr, 2 * idx + 2, uwu);
  }
  st[idx].ans = max(st[2*idx+1].ans, st[2*idx+2].ans);
  if(abs(st[idx].ans - st[2*idx+1].ans) < abs(st[idx].ans - st[2*idx+2].ans)) st[idx].id = st[2*idx+1].id;
  else st[idx].id = st[2*idx+2].id;
}

pair<long double, int> qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) return {st[idx].ans, st[idx].id};
  push_down(idx);
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  else {
    return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
  }
}

long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}

long long bit[MAXN];

// To use

void mul(int x, long long y) {
  x++;
  for(;x<MAXN;x+=x&-x) bit[x] = (bit[x] * y) % MOD;
}
void div(int x, long long y) {
  x++;
  long long invy = inv(y);
  for(;x<MAXN;x+=x&-x) bit[x] = (bit[x] * invy) % MOD;
}
long long prod(int x) {
  x++;
  long long ret = 1;
  for(;x; x-=x&-x) ret = (ret * bit[x]) % MOD;
  return ret;
}

void x_upd(int l, int r, long double v) {
  u(l, r, 0, MAXN - 1, 0, v);
}

long double thelog(int x) {
  return 1000.0 * log2(x);
}

int find_best_index() {
  return qu(0, n - 1, 0, MAXN - 1, 0).second;
}

int eval() {
  int fbi = find_best_index();
  long long ans = (prod(fbi) * y[fbi]) % MOD;
  //cout << fbi << ' ' << prod(fbi) << ' ' << y[fbi] << '\n';
  return (int) ans;
}

int init(int N, int X[], int Y[]) {
  n = N;
  build(0, MAXN - 1, 0);
  for(int i=0; i<n; i++) x[i] = X[i];
  for(int i=0; i<n; i++) y[i] = Y[i];
  for(int i=0; i<=n; i++) bit[i] = 1;
  for(int i=0; i<n; i++) mul(i, x[i]);
  long double thelogsum = 0;
  for(int i=0; i<n; i++) {
    thelogsum += thelog(x[i]);
    long double simp = thelogsum + thelog(y[i]);
    x_upd(i, i, simp);
  }

  return eval();
}

int updateX(int pos, int val) {
  div(pos, x[pos]);
  x_upd(pos, n - 1, thelog(val)-thelog(x[pos]));
  x[pos] = val;
  mul(pos, x[pos]);
  return eval();
}

int updateY(int pos, int val) {
  x_upd(pos, pos, thelog(val)-thelog(y[pos]));
  y[pos] = val;
  return eval();
}

Compilation message (stderr)

horses.cpp: In function 'void mul(int, long long int)':
horses.cpp:86:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   86 | void mul(int x, long long y) {
      |                 ~~~~~~~~~~^
horses.cpp:7:11: note: shadowed declaration is here
    7 | long long y[MAXN];
      |           ^
horses.cpp:86:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   86 | void mul(int x, long long y) {
      |          ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'void div(int, long long int)':
horses.cpp:90:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   90 | void div(int x, long long y) {
      |                 ~~~~~~~~~~^
horses.cpp:7:11: note: shadowed declaration is here
    7 | long long y[MAXN];
      |           ^
horses.cpp:90:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   90 | void div(int x, long long y) {
      |          ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'long long int prod(int)':
horses.cpp:95:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   95 | long long prod(int x) {
      |                ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'long double thelog(int)':
horses.cpp:106:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  106 | long double thelog(int x) {
      |                    ~~~~^
horses.cpp:6:11: note: shadowed declaration is here
    6 | long long x[MAXN];
      |           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:130:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |     thelogsum += thelog(x[i]);
      |                         ~~~^
horses.cpp:131:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  131 |     long double simp = thelogsum + thelog(y[i]);
      |                                           ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:140:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  140 |   x_upd(pos, n - 1, thelog(val)-thelog(x[pos]));
      |                                        ~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |   x_upd(pos, pos, thelog(val)-thelog(y[pos]));
      |                                      ~~~~~^

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