Submission #1161037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161037		akamizane	Growing Trees (BOI11_grow)	C++20	100 / 100	38 ms	2448 KiB

grow

#include<bits/stdc++.h>
 
using namespace std;

#define debug(...) 40

using ll = long long;
using pii = pair<int,int>;

#define int long long
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, a, n) for (int i = (a); i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}

void setIO(string s) {
  // freopen((s + ".inp").c_str(), "r", stdin);
  // freopen((s + ".out").c_str(), "w", stdout);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;

int n, q;

struct BIT{
  vector<int> bit;
  BIT(){}
  BIT(int n){bit = vector<int> (n + 5);}
  void up(int k, int x){
    // k++;
    for (; k < bit.size(); k += k & -k) bit[k] += x;
  }
  int get(int k){
    // k++;
    int ans = 0;
    for (; k > 0; k -= k & -k) ans += bit[k];
    return ans;
  }
int upb(int val){
  int lg = 17;
  int cur = 0, idx = 0;
  for (int i = lg; i >= 0; i--){
    if (idx + (1 << i) <= n && cur + bit[idx + (1 << i)] <= val){
      idx += 1 << i;
      cur += bit[idx];
    }
  }
  return idx;
}
  void inc(int l, int r){
    up(l, 1);
    up(r + 1, -1);
  }
};

int32_t main() {
  // setIO("cowbasic");
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(all(a));
  BIT bit(n + 1);
  for (int i = 1; i <= n; i++) bit.up(i, a[i] - a[i - 1]);
  while(q--){
    char t;
    int x, y;
    cin >> t >> x >> y;
    debug(t, x, y);
    if (t == 'F'){
      int l = bit.upb(y - 1) + 1;
      if (l > n) continue;
      int r = min(n, l + x - 1);
      int val = bit.get(r);
      int r1 = bit.upb(val), r2 = bit.upb(val - 1);
      bit.inc(l, r2);
      int l1 = max(r2 + 1, r1 - (x - (r2 - l + 1)) + 1);
      bit.inc(l1, r1);
    }
    else if (t == 'C'){
      cout << bit.upb(y) - bit.upb(x - 1) << "\n";
    }
  }
  return 0;
}

Compilation message (stderr)

grow.cpp: In function 'void setIO(std::string)':
grow.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10