Submission #582442

#	Time	Username	Problem	Language	Result	Execution time	Memory
582442		Shreyan_Paliwal	Growing Trees (BOI11_grow)	C++17	0 / 100	288 ms	5968 KiB

grow

// #include <bits/stdc++.h>

// using namespace std;

// const int maxnm = 100000;
// const int segnm = (1<<18);

// int n, m;
// int trees[maxnm];
// int ts[maxnm];

// int seg[segnm];
// int flag[segnm];

// void upd1(int p, int l, int r, int k) {
// 	if (k < l || r < k) return;
// 	if (l == r) {
// 		seg[p]++;
// 		return;
// 	}
// 	int mid = (l + r) >> 1;
// 	upd1(2*p, l, mid, k); upd1(2*p+1, mid+1, r, k);
// 	seg[p] = seg[2*p] + seg[2*p + 1];
// }

// void push(int p, int l, int r) {
// 	if (l == r) {
// 		flag[p] = 0;
// 		return;
// 	}
// 	int mid = (l + r) >> 1;
// 	seg[2*p] *= (flag[p] ^ 1); seg[2*p + 1] *= (flag[p] ^ 1);
// 	flag[2*p] = flag[2*p + 1] = flag[p];
// 	flag[p] = 0;
// }

// int upd2(int p, int l, int r, int mh, int R) {
// 	push(p, l, r);
// 	if (l <= mh) {
// 		if (seg[p] <= R) {
// 			seg[p] = 0; flag[p] = 1;
// 			return R - seg[p];
// 		}
// 		int mid = (l + r) >> 1;
// 		int x = upd2(2*p, l, mid, mh, R);
// 		if (x > 0) upd2(2*p + 1, mid+1, r, mh, R - x);
// 		return 0;
// 	}
// 	int mid = (l + r) >> 1;
// 	int x = upd2(2*p, l, mid, mh, R);
// 	if (x > 0) x = upd2(2*p+1, mid+1, r, mh, R - x);
// 	return x;
// }

// int qry(int p, int l, int r, int L, int R) {
// 	push(p, l, r);
// 	if (R < l || r < L) return 0;
// 	if (L <= l && r <= R) return seg[p];
// 	int mid = (l + r) >> 1;
// 	return qry(2*p, l, mid, L, R) + qry(2*p + 1, mid+1, r, L, R);
// }

// void print(int p, int l, int r) {
// 	push(p, l, r);
// 	if (l == r) {
// 		cout << seg[p] << " "; return;
// 	} int mid = (l+r)>>1;
// 	print(2*p, l, mid); print(2*p + 1, mid+1, r);
// }

// int main() {

// 	cin >> n >> m;
// 	for (int i = 0; i < n; i++) {
// 		cin >> trees[i];
// 		ts[i] = i;
// 	}

// 	sort(ts, ts+n, [](int a, int b){ return trees[a] < trees[b]; });

// 	int counter = 0; map<int, int> M;
// 	for (int i = 0; i < n; i++) {
// 		upd1(1, 0, n-1, counter);
// 		M[trees[ts[i]]] = counter;
// 		if (trees[ts[i]] < trees[ts[i + 1]]) counter++;
// 	}

// 	for (int i = 0; i < m; i++) {
// 		char t; int a, b; cin >> t >> a >> b;
// 		if (t == 'F') {
// 			upd2(1, 0, n-1, b, a);
// 			cout << "------------------" << endl;
// 			print(1, 0, n-1); cout << endl;
// 			cout << "------------------" << endl;
// 		} else {
// 			a = M[a], b = M[b];
// 			cout << a << " " << b << " ";
// 			cout << qry(1, 0, n-1, a, b) << '\n';
// 		}
// 	}





// 	return 0;
// }

#include <bits/stdc++.h>

using namespace std;

const int maxnm = 100000;
const int segnm = (1<<18);

int n, m;
int trees[maxnm];

pair<int,int> seg[segnm];
int flg[segnm];

void form(int p, int l, int r) {
  seg[p] = {max(seg[2*p].first, seg[2*p+1].first), min(seg[2*p].second, seg[2*p+1].second)};
}

void build(int p, int l, int r) {
  if (l == r) {
    // cout << p << " " << l << " " << r << " " << trees[l] << endl;
    seg[p] = {trees[l], trees[l]};
    // cout << seg[p].first << " " << seg[p].second << endl;
    return;
  }
  int mid = (l + r)/2;
  build(2*p, l, mid); build(2*p + 1, mid+1, r);
  form(p, l, r);
    // cout << seg[p].first << " " << seg[p].second << endl;

}

void push(int p, int l, int r) {
  if (l == r) { flg[p] = 0; return; }
  seg[2*p].first += flg[p]; seg[2*p+1].first += flg[p];
  seg[2*p].second += flg[p]; seg[2*p+1].second += flg[p];
  flg[2*p] += flg[p]; flg[2*p+1] += flg[p];
  flg[p] = 0;
}

void upd(int p, int l, int r, int L, int R) {
  push(p, l, r);
  if (r < L || R < l) return;
  if (L <= l && r <= R) {
    // cout << "UPD " << l << " " << r << " " << L << " " << R << endl;
    seg[p].first++; seg[p].second++;
    flg[p]++;
    return;
  }
  int mid = (l + r)/2;
  upd(2*p, l, mid, L, R);
  upd(2*p + 1, mid+1, r, L, R);
  form(p, l, r);
}

int qryMin(int p, int l, int r, int k) {
  push(p, l, r);
  if (l == r) return l;
  int mid = (l + r) / 2;
  if (seg[2*p].first < k) return qryMin(2*p+1, mid+1, r, k);
  else return qryMin(2*p, l, mid, k);
}

int qryMax(int p, int l, int r, int k) {
  push(p, l, r);
  if (l == r) return l;
  int mid = (l + r) / 2;
  if (seg[2*p+1].second > k) return qryMax(2*p, l, mid, k);
  else return qryMax(2*p + 1, mid+1, r, k);
}

void print(int p, int l, int r) {
  push(p, l, r);
  if (l == r) cout << p << " " << l << " " << r << " " << seg[p].first << " " << seg[p].second << endl;
  if (l == r) return;
  print(2*p, l, (l+r)/2);
  print(2*p+1, (l+r)/2+1, r);
}

int qry(int p, int l, int r, int k) {
  push(p, l, r);
  if (k < l || r < k) {
    return -2000000000;
  }
  if (l == r) {
    return seg[p].first;
  }
  int mid = (l + r)/2;
  return max(qry(2*p, l, mid, k), qry(2*p + 1, mid+1, r, k));
}

int main() {

  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> trees[i];

  sort(trees, trees + n);

  build(1, 0, n-1);
  // cout << endl;

  // print(1, 0, n-1);
  // cout << endl;

  // for (int j = 0; j < n; j++) cout << qry(1, 0, n-1, j) << " ";
  //     cout << endl;
  // cout << endl;
  for (int i = 0; i < m; i++) {
    char t; cin >> t; int a, b; cin >> a >> b;
    if (t == 'F') {
      int minstart = qryMin(1, 0, n-1, b);
      // cout << minstart << endl;
      if (minstart + a - 1 >= n) {
        // upd(1, 0, n-1, minstart, n-1);
        continue;
      }
      // cout << minstart + a - 1 << " " << 0 << " " << n-1 << endl;
      int k = qry(1, 0, n-1, minstart + a - 1);
      int maxstart = qryMin(1, 0, n-1, k);
      int maxend = qryMax(1, 0, n-1, k);
      if (minstart == maxstart) {
        // cout << minstart << " " << minstart + a - 1 << endl;
        upd(1, 0, n-1, minstart, minstart + a - 1);
        continue;
      }
      // cout << minstart << " " << maxstart << " " << maxend << endl;
      // cout << minstart << " " << maxstart -1 << " " << maxend - (maxstart - minstart) + 1 << " " << maxend << endl;
      upd(1, 0, n-1, minstart, maxstart - 1);
      upd(1, 0, n-1, maxend - (maxstart - minstart) + 1, maxend);
    } else {
      int c = qryMin(1, 0, n-1, a);
      int d = qryMax(1, 0, n-1, b);
      if (qry(1, 0, n-1, c) > b || qry(1, 0, n-1, d) < a) {
        cout << 0 << '\n';
        continue;
      }
      cout << d-c+1 << '\n';
    }
      // print(1, 0, n-1); cout << endl;
  }

  return 0;
}

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