Submission #609840

#	Time	Username	Problem	Language	Result	Execution time	Memory
609840		cjoa	Horses (IOI15_horses)	C++17	100 / 100	737 ms	70520 KiB

horses

#include "horses.h"

#include <vector>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long llong;

const int MOD = 1e9 + 7;

class SegmentTreeMax {
   int N;
   vector<int> A;
   vector<int> tree;
   void _preprocess(int node, int L, int R);
   void _update(int idx, int val, int node, int L, int R);
   int _query(int i, int j, int node, int L, int R) const;
public:
   void preprocess(const vector<int>& _A) {
      A = _A;
      N = A.size();
      tree = vector<int>(4*N, -1);
      _preprocess(1, 0, N-1);
   }
   void update(int idx, int val) {
      _update(idx, val, 1, 0, N-1);
   }

   int query(int i, int j) const {
      return _query(i, j, 1, 0, N-1);
   }
};

void SegmentTreeMax::_preprocess(int node, int L, int R) {
   if (L == R) {
      tree[node] = L;
      return;
   }
   _preprocess(2*node, L, (L+R)/2);
   _preprocess(2*node+1, (L+R)/2+1, R);
   int pL = tree[2*node], pR = tree[2*node+1];
   if (pL < 0)
      tree[node] = pR;
   else if (pR < 0)
      tree[node] = pL;
   else
      tree[node] = A[pL] >= A[pR] ? pL : pR;
}

void SegmentTreeMax::_update(int idx, int val, int node, int L, int R) {
   if (idx < L || idx > R)
      return;
   if (L == R) {
      A[L] = val;
   // tree[node] = L;
      return;
   }
   _update(idx, val, 2*node, L, (L+R)/2);
   _update(idx, val, 2*node+1, (L+R)/2+1, R);
   int pL = tree[2*node], pR = tree[2*node+1];
   if (pL < 0)
      tree[node] = pR;
   else if (pR < 0)
      tree[node] = pL;
   else
      tree[node] = A[pL] >= A[pR] ? pL : pR;
}

int SegmentTreeMax::_query(int i, int j, int node, int L, int R) const {
   if (i > R || j < L)
      return -1;
   if (i <= L && R <= j)
      return tree[node];
   int pL = _query(i, j, 2*node, L, (L+R)/2);
   int pR = _query(i, j, 2*node+1, (L+R)/2+1, R);
   if (pL < 0) return pR;
   else if (pR < 0) return pL;
   else return A[pL] >= A[pR] ? pL : pR;
}


class SegmentTreeMult {
   int N;
   vector<int> tree;
   void _preprocess(const vector<int>& A, int node, int L, int R);
   void _update(int idx, int val, int node, int L, int R);
   int _query(int i, int j, int node, int L, int R) const;
public:
   void preprocess(const vector<int>& A) {
      N = A.size();
      tree = vector<int>(4*N);
      _preprocess(A, 1, 0, N-1);
   }

   void update(int idx, int val) {
      _update(idx, val, 1, 0, N-1);
   }

   int query(int i, int j) const {
      return _query(i, j, 1, 0, N-1);
   }
};

void SegmentTreeMult::_preprocess(const vector<int>& A, int node, int L, int R) {
   if (L == R) {
      tree[node] = A[L];
      return;
   }
   _preprocess(A, 2*node, L, (L+R)/2);
   _preprocess(A, 2*node+1, (L+R)/2+1, R);
   tree[node] = (tree[2*node] * 1LL * tree[2*node+1]) % MOD;
}

void SegmentTreeMult::_update(int idx, int val, int node, int L, int R) {
   if (idx < L || idx > R)
      return;
   if (L == R) {
      tree[node] = val;
      return;
   }
   _update(idx, val, 2*node, L, (L+R)/2);
   _update(idx, val, 2*node+1, (L+R)/2+1, R);
   tree[node] = (tree[2*node] * 1LL * tree[2*node+1]) % MOD;
}

int SegmentTreeMult::_query(int i, int j, int node, int L, int R) const {
   if (i > R || j < L)
      return 1;
   if (i <= L && R <= j)
      return tree[node];
   int resL = _query(i, j, 2*node, L, (L+R)/2);
   int resR = _query(i, j, 2*node+1, (L+R)/2+1, R);
   return (resL * 1LL * resR) % MOD;
}

int N;
vector<int> X, Y;
vector<double> logX, logY;

int query(const set<int, greater<int> >& pos_not_ones,
          const SegmentTreeMult& st_mult, const SegmentTreeMax& st_max) {
   if (pos_not_ones.empty()) {
      return Y[st_max.query(0, N-1)];
   }

   vector<int> pos;
   for (auto it = pos_not_ones.begin(); it != pos_not_ones.end(); ++it) {
      pos.push_back(*it);
      if (int(pos.size()) >= 30)
         break;
   }
   reverse(pos.begin(), pos.end());
   pos.push_back(N);

   int best_p = 0, best_y = 0;
   double cur_log_prod = 0, best_log_prod = 0;

   if (pos.size() < 31) {
      int pos_max_y = st_max.query(0, pos[0]-1);
      best_log_prod = logY[pos_max_y];
      best_p = 0;
      best_y = Y[pos_max_y];
   }
   
   for (int i = 1; i < (int) pos.size(); ++i) {
      int p = pos[i-1];
      int q = pos[i];
      cur_log_prod += logX[p];
      int pos_max_y = st_max.query(p, q-1);
      double log_prod = cur_log_prod + logY[pos_max_y];
      if (best_log_prod < log_prod) {
         best_log_prod = log_prod;
         best_p = p;
         best_y = Y[pos_max_y];
      }
   }
   int res = (st_mult.query(0, best_p) * 1LL * best_y) % MOD;
   return res;
}

set<int, greater<int> > pos_not_ones;
SegmentTreeMult st_mult;
SegmentTreeMax  st_max;

int init(int N, int X[], int Y[]) {
   ::N = N;
   ::X = vector<int>(X, X+N);
   ::Y = vector<int>(Y, Y+N);
   pos_not_ones.clear();
   logX = vector<double>(N);
   logY = vector<double>(N);
   for (int i = 0; i < N; ++i) {
      if (X[i] != 1)
         pos_not_ones.insert(i);
      logX[i] = log(X[i]);
      logY[i] = log(Y[i]);
   }

   st_mult.preprocess(::X);
   st_max.preprocess(::Y);

   return query(pos_not_ones, st_mult, st_max);;
}


int updateX(int pos, int val) {	
    st_mult.update(pos, val);
    if (X[pos] == 1 && val > 1)
        pos_not_ones.insert(pos);
    else if (X[pos] > 1 && val == 1)
        pos_not_ones.erase(pos);
    X[pos] = val;
    logX[pos] = log(val);

    return query(pos_not_ones, st_mult, st_max);;
}

int updateY(int pos, int val) {
    st_max.update(pos, val);
    Y[pos] = val;
    logY[pos] = log(val);

    return query(pos_not_ones, st_mult, st_max);;
}

Compilation message (stderr)

horses.cpp: In member function 'void SegmentTreeMax::preprocess(const std::vector<int>&)':
horses.cpp:24:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   24 |       N = A.size();
      |           ~~~~~~^~
horses.cpp: In member function 'void SegmentTreeMult::preprocess(const std::vector<int>&)':
horses.cpp:93:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   93 |       N = A.size();
      |           ~~~~~~^~
horses.cpp: In member function 'void SegmentTreeMult::_preprocess(const std::vector<int>&, int, int, int)':
horses.cpp:114:55: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
  114 |    tree[node] = (tree[2*node] * 1LL * tree[2*node+1]) % MOD;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void SegmentTreeMult::_update(int, int, int, int, int)':
horses.cpp:126:55: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
  126 |    tree[node] = (tree[2*node] * 1LL * tree[2*node+1]) % MOD;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int SegmentTreeMult::_query(int, int, int, int, int) const':
horses.cpp:136:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  136 |    return (resL * 1LL * resR) % MOD;
      |           ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int query(const std::set<int, std::greater<int> >&, const SegmentTreeMult&, const SegmentTreeMax&)':
horses.cpp:180:56: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  180 |    int res = (st_mult.query(0, best_p) * 1LL * best_y) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:188:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
  188 | int init(int N, int X[], int Y[]) {
      |                          ~~~~^~~
horses.cpp:140:16: note: shadowed declaration is here
  140 | vector<int> X, Y;
      |                ^
horses.cpp:188:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
  188 | int init(int N, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:140:13: note: shadowed declaration is here
  140 | vector<int> X, Y;
      |             ^
horses.cpp:188:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  188 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:139:5: note: shadowed declaration is here
  139 | int N;
      |     ^

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