oj.uz

Submission #1077864

# Submission time Handle Problem Language Result Execution time Memory
1077864 2024-08-27T09:52:10 Z juicy Horses (IOI15_horses) C++17
100 / 100
 464 ms 54428 KB 
#include "horses.h"

#include <bits/stdc++.h>

const int N = 5e5, MD = 1e9 + 7;

int n;
int a[N], prv[N], ma[4 * N], s[4 * N];
std::set<int> st;

void upd(int i, int x, int *s, int pul(int, int), int id = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    s[id] = x;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, s, pul, id * 2, l, md);
  } else {
    upd(i, x, s, pul, id * 2 + 1, md + 1, r);
  }
  s[id] = pul(s[id * 2], s[id * 2 + 1]);
} 

int qry(int u, int v, int *s, int pul(int, int), int id = 1, int l = 0, int r = n - 1) {
  if (u <= l && r <= v) {
    return s[id];
  }
  int md = (l + r) / 2;
  if (v <= md) {
    return qry(u, v, s, pul, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, s, pul, id * 2 + 1, md + 1, r);
  }
  return pul(qry(u, v, s, pul, id * 2, l, md), qry(u, v, s, pul, id * 2 + 1, md + 1, r));
}

int mul(int a, int b) {
  return (long long) a * b % MD;
}

int max(int a, int b) {
  return std::max(a, b);
}

int get() {
  if (!st.size()) {
    return ma[1];
  }
  int p = *st.rbegin(), prod = 1;
  std::vector<int> cands;
  while (~p) {
    cands.push_back(p);
    if (a[p] > MD / prod) {
      break;
    }
    prod *= a[p];
    p = prv[p];
  } 
  if (p == -1 && cands.back()) {
    cands.push_back(0);
  }
  reverse(cands.begin(), cands.end());
  int base = qry(0, cands[0], s, mul);
  long long best = qry(cands[0], cands.size() == 1 ? n - 1 : cands[1] - 1, ma, max);
  prod = 1;
  for (int i = 1; i < cands.size(); ++i) {
    prod *= a[cands[i]];
    int j = i + 1 == cands.size() ? n - 1 : cands[i + 1] - 1;
    best = std::max(best, (long long) qry(cands[i], j, ma, max) * prod);
  }

  return best % MD * base % MD;
}

int init(int n, int *x, int *y) {
  ::n = n;
  for (int i = 0; i < n; ++i) {
    if (x[i] > 1) {
      prv[i] = !st.size() ? -1 : *st.rbegin();
      st.insert(i);
    }
    upd(i, x[i], s, mul);
    upd(i, y[i], ma, max);
  }
  for (int i = 0; i < n; ++i) {
    a[i] = x[i];
  }
  return get();
}

void ers(int i) {
  auto it = st.find(i);
  it = st.erase(it);
  if (it != st.end()) {
    prv[*it] = it == st.begin() ? -1 : *prev(it);
  }
}

void add(int i) {
  auto it = st.insert(i).first;
  prv[*it] = it == st.begin() ? -1 : *prev(it);
  ++it;
  if (it != st.end()) {
    prv[*it] = i;
  }
}

int updateX(int i, int x) {	
  if (x == 1 && a[i] > 1) {
    ers(i);
  } 
  if (x > 1 && a[i] == 1) {
    add(i);
  }
  upd(i, a[i] = x, s, mul);
  return get();
}

int updateY(int i, int x) {
  upd(i, x, ma, max);
  return get();
}

Compilation message

horses.cpp: In function 'void upd(int, int, int*, int (*)(int, int), int, int, int)':
horses.cpp:11:29: warning: declaration of 's' shadows a global declaration [-Wshadow]
   11 | void upd(int i, int x, int *s, int pul(int, int), int id = 1, int l = 0, int r = n - 1) {
      |                        ~~~~~^
horses.cpp:8:30: note: shadowed declaration is here
    8 | int a[N], prv[N], ma[4 * N], s[4 * N];
      |                              ^
horses.cpp: In function 'int qry(int, int, int*, int (*)(int, int), int, int, int)':
horses.cpp:25:28: warning: declaration of 's' shadows a global declaration [-Wshadow]
   25 | int qry(int u, int v, int *s, int pul(int, int), int id = 1, int l = 0, int r = n - 1) {
      |                       ~~~~~^
horses.cpp:8:30: note: shadowed declaration is here
    8 | int a[N], prv[N], ma[4 * N], s[4 * N];
      |                              ^
horses.cpp: In function 'int mul(int, int)':
horses.cpp:39:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   39 | int mul(int a, int b) {
      |         ~~~~^
horses.cpp:8:5: note: shadowed declaration is here
    8 | int a[N], prv[N], ma[4 * N], s[4 * N];
      |     ^
horses.cpp:40:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |   return (long long) a * b % MD;
      |          ~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int max(int, int)':
horses.cpp:43:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   43 | int max(int a, int b) {
      |         ~~~~^
horses.cpp:8:5: note: shadowed declaration is here
    8 | int a[N], prv[N], ma[4 * N], s[4 * N];
      |     ^
horses.cpp: In function 'int get()':
horses.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i = 1; i < cands.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~
horses.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     int j = i + 1 == cands.size() ? n - 1 : cands[i + 1] - 1;
      |             ~~~~~~^~~~~~~~~~~~~~~
horses.cpp:74:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |   return best % MD * base % MD;
      |          ~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:77:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   77 | int init(int n, int *x, int *y) {
      |          ~~~~^
horses.cpp:7:5: note: shadowed declaration is here
    7 | int n;
      |     ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 2488 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 440 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 412 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 2520 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 2 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 2 ms 2508 KB Output is correct
32 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 44708 KB Output is correct
2 Correct 381 ms 53512 KB Output is correct
3 Correct 336 ms 44884 KB Output is correct
4 Correct 370 ms 48568 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 440 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 444 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 360 KB Output is correct
23 Correct 2 ms 2500 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 175 ms 21632 KB Output is correct
34 Correct 167 ms 20364 KB Output is correct
35 Correct 308 ms 52048 KB Output is correct
36 Correct 303 ms 50644 KB Output is correct
37 Correct 185 ms 17632 KB Output is correct
38 Correct 215 ms 31564 KB Output is correct
39 Correct 163 ms 16432 KB Output is correct
40 Correct 280 ms 45976 KB Output is correct
41 Correct 173 ms 16596 KB Output is correct
42 Correct 179 ms 16512 KB Output is correct
43 Correct 277 ms 47476 KB Output is correct
44 Correct 272 ms 46816 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 448 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Correct 1 ms 484 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 444 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 400 ms 45260 KB Output is correct
34 Correct 370 ms 54428 KB Output is correct
35 Correct 314 ms 44672 KB Output is correct
36 Correct 340 ms 49604 KB Output is correct
37 Correct 184 ms 20528 KB Output is correct
38 Correct 168 ms 20556 KB Output is correct
39 Correct 295 ms 50992 KB Output is correct
40 Correct 289 ms 50828 KB Output is correct
41 Correct 203 ms 17604 KB Output is correct
42 Correct 214 ms 31476 KB Output is correct
43 Correct 152 ms 16500 KB Output is correct
44 Correct 279 ms 45776 KB Output is correct
45 Correct 177 ms 17564 KB Output is correct
46 Correct 166 ms 16564 KB Output is correct
47 Correct 284 ms 46172 KB Output is correct
48 Correct 266 ms 46164 KB Output is correct
49 Correct 238 ms 24696 KB Output is correct
50 Correct 227 ms 23632 KB Output is correct
51 Correct 359 ms 53844 KB Output is correct
52 Correct 347 ms 52180 KB Output is correct
53 Correct 464 ms 20748 KB Output is correct
54 Correct 290 ms 35268 KB Output is correct
55 Correct 227 ms 17492 KB Output is correct
56 Correct 347 ms 47696 KB Output is correct
57 Correct 280 ms 18368 KB Output is correct
58 Correct 314 ms 18736 KB Output is correct
59 Correct 303 ms 46172 KB Output is correct