oj.uz

Submission #890702

# Submission time Handle Problem Language Result Execution time Memory
890702 2023-12-21T18:49:39 Z AkibAzmain Horses (IOI15_horses) C++17
34 / 100
 1500 ms 21612 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;

const ll MOD = ((ll) 1e9) + 7;

ll n;
vector < ll > ma;
vector < ll > bit;
int sts = 1;
vector < ll > mst;
set < ll > cs;

ll
binpow (ll a, ll b)
{
  ll ans = 1;
  while (b)
    {
      if (b % 2) (ans *= a) %= MOD;
      b /= 2;
      if (b) (a *= a) %= MOD;
    }
  return ans;
}

ll
bitp (ll x)
{
  ll ans = 1;
  for (int i = 0; i <= x; ++i) (ans *= ma[i]) %= MOD;
  // while (x >= 0)
  //   {
  //     (ans *= bit[x]) %= MOD;
  //     x -= (x + 1) & -(x + 1);
  //   }
  return ans;
}

ll
bitr (ll l, ll r)
{
  ll ans = bitp (r);
  if (l) (ans *= binpow (bitp (l - 1), MOD - 2)) %= MOD;
  return ans;
}

ll
stm (ll l, ll r)
{
  l += sts, r += sts;
  ll mx = -1;
  while (l <= r)
    {
      if (l % 2 == 1) mx = max (mx, mst[l++]);
      if (r % 2 == 0) mx = max (mx, mst[r--]);
      l /= 2, r /= 2;
    }
  return mx;
}

int
calc ()
{
  auto it = cs.end (), pit = prev (it);
  ll vl = 0;
  while (vl < MOD)
    {
      --it, --pit;
      vl = max (vl, mst[sts + *it]);
      vl *= ma[*it];
      if (vl >= MOD) break;
      if (*it && *pit + 1 <= *it - 1)
        vl = max (vl, stm (*pit + 1, *it - 1));
      if (!*pit) ++pit;
      if (!*it) break;
    }
  vl %= MOD;
  if (*it)
    (vl *= bitp (*it - 1)) %= MOD;
  return vl;
}

int init(int N, int x[], int y[]) {
  n = N;
  ma.resize (n);
  bit.resize (n);
  while (sts < n) sts *= 2;
  mst.resize (sts * 2);
  for (int i = 0; i < n; ++i)
    {
      if (x[i] > 1) cs.insert (i);
      ma[i] = x[i];
      mst[sts + i] = y[i];
      bit[i] = x[i] * (i ? bitr (i - ((i + 1) & -(i + 1)) + 1, i - 1) : 1ll);
    }
  for (int i = sts - 1; i > 0; --i) mst[i] = max (mst[i * 2], mst[i * 2 + 1]);
  cs.insert (0);
  cs.insert (n - 1);
  return calc ();
}

int updateX(int pos, int val) {
  cs.erase (pos);
  if (val > 1) cs.insert (pos);
  ll dl = val * binpow (ma[pos], MOD - 2) % MOD;
  ma[pos] = val;
  for (int i = pos; i < n; i += (i + 1) & -(i + 1)) (bit[i] *= dl) %= MOD;
  cs.insert (0);
  cs.insert (n - 1);
  return calc ();
}

int updateY(int pos, int val) {
  int i = sts + pos;
  mst[i] = val;
  for (i /= 2; i > 0; i /= 2) mst[i] = max (mst[i * 2], mst[i * 2 + 1]);
  return calc ();
}

Compilation message

horses.cpp: In function 'int calc()':
horses.cpp:82:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   82 |   return vl;
      |          ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 21612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 9 ms 344 KB Output is correct
24 Correct 10 ms 348 KB Output is correct
25 Correct 10 ms 348 KB Output is correct
26 Correct 9 ms 348 KB Output is correct
27 Correct 9 ms 472 KB Output is correct
28 Correct 10 ms 348 KB Output is correct
29 Correct 5 ms 468 KB Output is correct
30 Correct 8 ms 344 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 7 ms 468 KB Output is correct
33 Execution timed out 1576 ms 20316 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 9 ms 348 KB Output is correct
24 Correct 9 ms 348 KB Output is correct
25 Correct 9 ms 348 KB Output is correct
26 Correct 9 ms 348 KB Output is correct
27 Correct 9 ms 344 KB Output is correct
28 Correct 9 ms 348 KB Output is correct
29 Correct 5 ms 348 KB Output is correct
30 Correct 8 ms 348 KB Output is correct
31 Correct 5 ms 348 KB Output is correct
32 Correct 7 ms 348 KB Output is correct
33 Execution timed out 1586 ms 21256 KB Time limit exceeded
34 Halted 0 ms 0 KB -