oj.uz

Submission #609840

# Submission time Handle Problem Language Result Execution time Memory
609840 2022-07-28T00:52:01 Z cjoa Horses (IOI15_horses) C++17
100 / 100
 737 ms 70520 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 292 KB Output is correct
15 Correct 0 ms 288 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 288 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 284 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 284 KB Output is correct
13 Correct 0 ms 288 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 288 KB Output is correct
16 Correct 0 ms 288 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 5 ms 388 KB Output is correct
24 Correct 4 ms 296 KB Output is correct
25 Correct 4 ms 432 KB Output is correct
26 Correct 4 ms 320 KB Output is correct
27 Correct 4 ms 300 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 5 ms 340 KB Output is correct
31 Correct 3 ms 464 KB Output is correct
32 Correct 4 ms 300 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 60048 KB Output is correct
2 Correct 655 ms 70516 KB Output is correct
3 Correct 622 ms 61800 KB Output is correct
4 Correct 652 ms 65636 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 292 KB Output is correct
7 Correct 0 ms 292 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 292 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 284 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 288 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 288 KB Output is correct
23 Correct 4 ms 340 KB Output is correct
24 Correct 6 ms 340 KB Output is correct
25 Correct 6 ms 340 KB Output is correct
26 Correct 4 ms 340 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 4 ms 428 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 5 ms 340 KB Output is correct
33 Correct 208 ms 34112 KB Output is correct
34 Correct 115 ms 37740 KB Output is correct
35 Correct 226 ms 67896 KB Output is correct
36 Correct 227 ms 67932 KB Output is correct
37 Correct 112 ms 35916 KB Output is correct
38 Correct 155 ms 48584 KB Output is correct
39 Correct 48 ms 35532 KB Output is correct
40 Correct 210 ms 63016 KB Output is correct
41 Correct 72 ms 35688 KB Output is correct
42 Correct 90 ms 35728 KB Output is correct
43 Correct 181 ms 63368 KB Output is correct
44 Correct 177 ms 63356 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 288 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 284 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 284 KB Output is correct
18 Correct 0 ms 288 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 5 ms 340 KB Output is correct
24 Correct 5 ms 340 KB Output is correct
25 Correct 5 ms 340 KB Output is correct
26 Correct 5 ms 340 KB Output is correct
27 Correct 7 ms 296 KB Output is correct
28 Correct 5 ms 296 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 6 ms 428 KB Output is correct
31 Correct 4 ms 304 KB Output is correct
32 Correct 4 ms 360 KB Output is correct
33 Correct 696 ms 59976 KB Output is correct
34 Correct 701 ms 70520 KB Output is correct
35 Correct 657 ms 61808 KB Output is correct
36 Correct 659 ms 65644 KB Output is correct
37 Correct 120 ms 37672 KB Output is correct
38 Correct 93 ms 37672 KB Output is correct
39 Correct 232 ms 67952 KB Output is correct
40 Correct 223 ms 67864 KB Output is correct
41 Correct 109 ms 35824 KB Output is correct
42 Correct 140 ms 48584 KB Output is correct
43 Correct 47 ms 35644 KB Output is correct
44 Correct 204 ms 63004 KB Output is correct
45 Correct 67 ms 35608 KB Output is correct
46 Correct 85 ms 35660 KB Output is correct
47 Correct 196 ms 63332 KB Output is correct
48 Correct 163 ms 63340 KB Output is correct
49 Correct 721 ms 40704 KB Output is correct
50 Correct 549 ms 40700 KB Output is correct
51 Correct 673 ms 69888 KB Output is correct
52 Correct 653 ms 69400 KB Output is correct
53 Correct 737 ms 39116 KB Output is correct
54 Correct 610 ms 52640 KB Output is correct
55 Correct 166 ms 36720 KB Output is correct
56 Correct 683 ms 64840 KB Output is correct
57 Correct 379 ms 37292 KB Output is correct
58 Correct 543 ms 37824 KB Output is correct
59 Correct 192 ms 63316 KB Output is correct