제출 #521347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521347		Alex_tz307	Horses (IOI15_horses)	C++17	17 / 100	352 ms	71924 KiB

horses

#include <bits/stdc++.h>
/// #include "horses.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, A[1 + kN], B[1 + kN], prod[1 + kN];
ld sum[1 + kN];

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) {
      t[x] = {sum[lx] + log(B[lx]), 0, mult(prod[lx], 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, int len, ld sum, int prod) {
    t[x].maxSum += sum * len;
    multSelf(t[x].maxProd, Pow(prod, len));
    t[x].lazySum += sum;
    multSelf(t[x].maxProd, prod);
  }

  void push(int x, int lx, int rx) {
    int mid = (lx + rx) / 2;
    int len[] = {mid - lx + 1, rx - mid};
    for (int i = 0; i < 2; ++i) {
      updateNode(x * 2 + i, len[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, rx - lx + 1, lazySum, lazyProd);
      return;
    }
    push(x, lx, rx);
    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;
  prod[0] = 1;
  for (int i = 1; i <= n; ++i) {
    A[i] = X[i - 1];
    B[i] = Y[i - 1];
    sum[i] = sum[i - 1] + log(A[i]);
    prod[i] = mult(prod[i - 1], A[i]);
  }
  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;
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'void multSelf(int&, const int&)':
horses.cpp:22:22: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
   22 |   x = (int64_t)x * y % mod;
      |       ~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void ST::updateNode(int, int, ld, int)':
horses.cpp:90:47: warning: declaration of 'prod' shadows a global declaration [-Wshadow]
   90 |   void updateNode(int x, int len, ld sum, int prod) {
      |                                           ~~~~^~~~
horses.cpp:65:30: note: shadowed declaration is here
   65 | int n, A[1 + kN], B[1 + kN], prod[1 + kN];
      |                              ^~~~
horses.cpp:90:38: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
   90 |   void updateNode(int x, int len, ld sum, int prod) {
      |                                   ~~~^~~
horses.cpp:66:4: note: shadowed declaration is here
   66 | ld sum[1 + kN];
      |    ^~~

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