oj.uz

Submission #991347

# Submission time Handle Problem Language Result Execution time Memory
991347 2024-06-02T07:22:06 Z megatron10 Growing Trees (BOI11_grow) C++17
100 / 100
 49 ms 1620 KB 
#include <bits/stdc++.h>
#define ull uint64_t
#define ll long long int
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
#define mx5 100005
#define mx52 200005
#define mx6 1000005
#define mod 1000000007
#define smod 998244353
#define nfs                     \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x)
{
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)             \
  cerr << "[" << #x << "] = ["; \
  _print(x)
#else
#define debug(x...)
#endif

template <typename T>
bool MinPlace(T &a, const T &b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}

template <typename T>
bool MaxPlace(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

template <typename S, typename T>
ostream &operator<<(ostream &out, const pair<S, T> &p)
{
  out << "{" << p.ff << ", " << p.ss << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v)
{
  out << "[";
  for (int i = 0; i < (int)v.size(); i++)
  {
    out << v[i];
    if (i != (int)v.size() - 1)
      out << ", ";
  }
  out << "]";
  return out;
}

template <typename T = ll>
class BIT
{
  int n;
  vector<T> v;

public:
  BIT(int n) : n(n)
  {
    v.resize(n + 1, 0);
  }

  void inc(int pos, T delta = 1)
  {
    for (int i = pos; i <= n; i += i & (-i))
      v[i] += delta;
  }

  void dec(int pos, T delta = 1)
  {
    inc(pos, -delta);
  }

  T qry(int r)
  {
    T ret = 0;
    for (int i = r; i; i = i & (i - 1))
      ret += v[i];
    return ret;
  }

  T rangeQry(int l, int r)
  {
    return qry(r) - qry(l - 1);
  }

  void upd(int pos, T val)
  {
    inc(pos, val - pointQry(pos));
  }

  T pointQry(int pos)
  {
    return qry(pos) - qry(pos - 1);
  }

  int geq(T val)
  {
    int i = 0;
    for (int b = 31 - __builtin_clz(n); b >= 0; b--)
    {
      int t = i + (1 << b);
      if (t <= n and v[t] < val)
      {
        val -= v[t];
        i = t;
      }
    }
    return i + 1;
  }
};

int main()
{
  nfs;
  int n, m;
  cin >> n >> m;
  vi h(n);
  for (int i = 0; i < n; i++)
    cin >> h[i];
  sort(h.begin(), h.end());
  BIT<int> b(n);
  for (int i = 0, p = 0; i < n; p = h[i++])
    if (h[i] != p)
      b.inc(i + 1, h[i] - p);
  for (int i = 0; i < m; i++)
  {
    char type;
    cin >> type;
    if (type == 'C')
    {
      // Stats
      int minm, maxm;
      cin >> minm >> maxm;
      cout << b.geq(maxm + 1) - b.geq(minm) << "\n";
      continue;
    }
    // Fertilizer
    int ci, hi;
    cin >> ci >> hi;
    int s = b.geq(hi);
    MinPlace(ci, n + 1 - s);
    int e = s + ci - 1;
    int ev = b.qry(e);
    int nextPos = b.geq(ev + 1);
    if (nextPos != e + 1)
    {
      int firstPos = b.geq(ev), cbig = (e - (firstPos - 1));
      b.inc(nextPos - cbig);
      b.dec(nextPos);
      e = firstPos - 1;
    }
    b.inc(s);
    b.dec(e + 1);
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1364 KB Output is correct
2 Correct 45 ms 1116 KB Output is correct
3 Correct 30 ms 1116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 21 ms 612 KB Output is correct
6 Correct 24 ms 616 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 13 ms 680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 764 KB Output is correct
2 Correct 25 ms 848 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 16 ms 556 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 856 KB Output is correct
2 Correct 27 ms 852 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 25 ms 820 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1116 KB Output is correct
2 Correct 42 ms 1112 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 20 ms 1016 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1140 KB Output is correct
2 Correct 41 ms 1208 KB Output is correct
3 Correct 22 ms 860 KB Output is correct
4 Correct 8 ms 604 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1116 KB Output is correct
2 Correct 28 ms 1580 KB Output is correct
3 Correct 24 ms 856 KB Output is correct
4 Correct 8 ms 604 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1240 KB Output is correct
2 Correct 41 ms 1116 KB Output is correct
3 Correct 16 ms 1116 KB Output is correct
4 Correct 26 ms 1116 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1364 KB Output is correct
2 Correct 49 ms 1508 KB Output is correct
3 Correct 39 ms 1116 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1620 KB Output is correct