Submission #105806

#TimeUsernameProblemLanguageResultExecution timeMemory
105806xiaowuc1Growing Trees (BOI11_grow)C++14
100 / 100
180 ms4728 KiB
#include <algorithm> #include <cassert> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, pii> pipii; typedef vector<vector<ll>> matrix; const int RAGETREE_SZ = 100005; int n; // max value in subinterval int ragetree[4 * RAGETREE_SZ]; int ragetreelazy[4 * RAGETREE_SZ]; void pushdown(int idx) { ragetreelazy[2*idx] += ragetreelazy[idx]; ragetreelazy[2*idx+1] += ragetreelazy[idx]; ragetreelazy[idx] = 0; } void pullup(int idx) { ragetree[idx] = max(ragetree[2*idx] + ragetreelazy[2*idx], ragetree[2*idx+1] + ragetreelazy[2*idx+1]); } void inc(int idx, int lhs, int rhs, int a, int b) { if(lhs >= a && rhs <= b) { ragetreelazy[idx]++; return; } pushdown(idx); int mid = (lhs+rhs)/2; if(mid >= a) inc(2*idx, lhs, mid, a, b); if(mid+1 <= b) inc(2*idx+1, mid+1, rhs, a, b); pullup(idx); } // increment everything in indices [lhs, rhs] by 1 void inc(int lhs, int rhs) { inc(1, 0, n-1, lhs, rhs); } int get(int idx, int lhs, int rhs, int i) { if(lhs == rhs) return ragetree[idx] + ragetreelazy[idx]; pushdown(idx); int ret = -1; int mid = (lhs+rhs)/2; if(i <= mid) ret = get(2*idx, lhs, mid, i); else ret = get(2*idx+1, mid+1, rhs, i); assert(ret >= 0); pullup(idx); return ret; } // return ith entry int get(int i) { return get(1, 0, n-1, i); } int get_le_count(int idx, int lhs, int rhs, int v) { if(ragetree[idx] + ragetreelazy[idx] <= v) return rhs; if(lhs == rhs) return -1; pushdown(idx); int ret = -1; int mid = (lhs+rhs)/2; if(ragetree[2*idx]+ragetreelazy[2*idx] <= v) { ret = max(mid, get_le_count(2*idx+1, mid+1, rhs, v)); } else { ret = get_le_count(2*idx, lhs, mid, v); } pullup(idx); return ret; } // return largest index <= v, -1 if none exists int get_le_idx(int v) { int ret = get_le_count(1, 0, n-1, v); // cout << "largest index <= " << v << " is apparently " << ret << endl; return ret; } int get_ge_count(int idx, int lhs, int rhs, int v) { if(ragetree[idx] + ragetreelazy[idx] < v) return n; if(lhs == rhs) return lhs; pushdown(idx); int ret = n; int mid = (lhs+rhs)/2; if(ragetree[2*idx] + ragetreelazy[2*idx] >= v) { ret = get_ge_count(2*idx, lhs, mid, v); } else { ret = get_ge_count(2*idx+1, mid+1, rhs, v); } pullup(idx); return ret; } // return smallest index >= v, n if none exists int get_ge_idx(int v) { return get_ge_count(1, 0, n-1, v); } void init(int idx, int lhs, int rhs, vector<int>& v) { if(lhs >= v.size()) return; if(lhs == rhs) { ragetree[idx] = v[lhs]; } else { int mid = (lhs+rhs)/2; init(2*idx, lhs, mid, v); init(2*idx+1, mid+1, rhs, v); pullup(idx); } } void init(vector<int>& v) { init(1, 0, n-1, v); } // increase the k smallest things >= h void update(int k, int h) { // cout << "processing " << k << " " << h << endl; int lhs = get_ge_idx(h); if(lhs == n) return; if(lhs + k - 1 >= n-1) { inc(lhs, n-1); return; } int lowestH = get(lhs); // cout << "lowest at this point is " << lhs << " index with height " << lowestH << endl; int largestH = get(min(n-1, lhs + k-1)); // cout << "largest height that will be affected is " << largestH << endl; int rhs = get_le_idx(largestH); if(lowestH < largestH) { // increment everything less int nrhs = get_le_idx(largestH-1); // cout << "small increment interval is " << lhs << " " << rhs << endl; assert(lhs <= nrhs); assert(nrhs - lhs + 1 <= k); inc(lhs, nrhs); k -= nrhs-lhs+1; } // increment the largest largestH values // cout << "still need to increment " << k << " at height " << largestH << endl; // cout << "largest index for this is " << rhs << endl; int nlhs = rhs-k+1; assert(nlhs >= lhs); inc(nlhs, rhs); } int query(int lhs, int rhs) { return get_le_idx(rhs) - get_le_idx(lhs-1); } void solve() { int m; cin >> n >> m; vector<int> v; v.resize(n); for(int i = 0; i < n; i++) cin >> v[i]; sort(v.begin(), v.end()); init(v); while(m--) { string s; cin >> s; if(s == "F") { int k, h; cin >> k >> h; update(k, h); } else { int lhs, rhs; cin >> lhs >> rhs; cout << query(lhs, rhs) << "\n"; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); /* int t; cin >> t; for(int i = 1; i <= t; i++) { cout << "Case #" << i << ": "; solve(); } */ solve(); }

Compilation message (stderr)

grow.cpp: In function 'void init(int, int, int, std::vector<int>&)':
grow.cpp:106:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lhs >= v.size()) return;
     ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...