제출 #1198448

#제출 시각아이디문제언어결과실행 시간메모리
1198448TheSahibBigger segments (IZhO19_segments)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; // Fenwick tree for range‐maximum queries struct Fenwick { int n; vector<int> f; Fenwick(int _n): n(_n), f(n+1, 0) {} // point update: set f[i] = max(f[i], v) void update(int i, int v) { for(; i <= n; i += i & -i) f[i] = max(f[i], v); } // prefix query: max over f[1..i] int query(int i) const { int r = 0; for(; i > 0; i -= i & -i) r = max(r, f[i]); return r; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<ll> a(N), S(N+1, 0); for(int i = 0; i < N; i++){ cin >> a[i]; S[i+1] = S[i] + a[i]; } // 1) coordinate‐compress all prefix‐sums S[0..N] vector<ll> all = S; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); auto idx = [&](ll x){ return int(lower_bound(all.begin(), all.end(), x) - all.begin()) + 1; }; // 2) bestSum[d] = minimum prefix‐sum S[j] at which we can form d segments vector<ll> bestSum(N+2, LLONG_MAX); bestSum[0] = 0; // 3) Fenwick tree will store, for each “key” K_j = 2*S[j] - bestSum[d_j], the value d_j // so that querying up to S[i] gives the max d_j with K_j <= S[i]. // Because K_j may not be in our compressed array, we’ll separately compress the set of // all possible keys as we go, by inserting (2*S[j] - bestSum[d_j]) into a second list. // // But we can avoid a second compression if we notice that: // K_j <= S[i] // ⇔ 2*S[j] - bestSum[d_j] <= S[i] // ⇔ S[j] <= (S[i] + bestSum[d_j]) / 2 // // However, that mixes d_j inside the bound, so we still need the original trick. // // For clarity and speed in contest, here’s the standard two‐Fenwick approach: // Prepare to collect all keys vector<ll> keys; keys.reserve(N+1); // initial j=0: d_j=0, bestSum[0]=0 -> key = 2*S[0] - 0 = 0 keys.push_back(0); for(int j = 1; j <= N; j++){ // we’ll later fill in key for each j once we know d_j // but for size we can push a placeholder keys.push_back(0); } // we will fill keys[j] = 2*S[j] - bestSum[d_j] after we compute d_j, // so let's do that on the fly, but we need the Fenwick size upfront: // to be safe, we’ll just compress over the union of all S[] and all (2*S[j]-anything), // but that’s tricky. Instead, we’ll do this: // — first pass: assume d_j <= N, bestSum[d_j] <= max S, so key <= 2*maxS. // — we can compress the range [minKey..maxKey] by noticing it’s still O(N). // // Actually the simplest is: we know every time we update bestSum[d+1] = S[i], the // corresponding key = 2*S[i] - bestSum[d] is ≥ S[i] (since bestSum[d] ≤ S[i]). // So all keys we ever produce lie in [min S .. 2*max S]. // We can collect them in a vector during the loop, then rebuild Fenwick. // Instead, let's do two‐pass: // Pass 1: compute dp_i and bestSum, collect keys. // Pass 2: compress keys and replay updates into Fenwick to answer. // PASS 1: compute dp_i and bestSum, collect raw key values vector<int> dp(N+1, 0); for(int i = 1; i <= N; i++){ // find best d with bestSum[d] <= S[i] by binary search int lo = 0, hi = i; while(lo < hi){ int mid = (lo + hi + 1) >> 1; if(bestSum[mid] <= S[i]) lo = mid; else hi = mid - 1; } dp[i] = lo; // update bestSum for d+1 bestSum[lo+1] = min(bestSum[lo+1], S[i]); // record the key for this j=i ll key = 2*S[i] - bestSum[lo]; keys[i] = key; } // Now compress all unique key values alongside S[i] vector<ll> allKeys = keys; sort(allKeys.begin(), allKeys.end()); allKeys.erase(unique(allKeys.begin(), allKeys.end()), allKeys.end()); auto keyIdx = [&](ll x){ return int(lower_bound(allKeys.begin(), allKeys.end(), x) - allKeys.begin()) + 1; }; // Build Fenwick over key‐indices Fenwick fenw((int)allKeys.size()); // Re‐initialize bestSum & answer, then replay fill(bestSum.begin(), bestSum.end(), LLONG_MAX); bestSum[0] = 0; int answer = 0; // j=0 initial state fenw.update(keyIdx(0), 0); for(int i = 1; i <= N; i++){ // dp_i is exactly the best we can get by querying all keys ≤ S[i] // i.e. find the last key-value index such that key ≤ S[i] int pos = int(upper_bound(allKeys.begin(), allKeys.end(), S[i]) - allKeys.begin()); int bestd = fenw.query(pos); answer = max(answer, bestd); // now update for j=i: we can form bestd+1 segments ending here // key = keys[i] int kpos = keyIdx(keys[i]); fenw.update(kpos, bestd+1); } cout << answer << "\n"; return 0; }
#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...