Submission #730127

#TimeUsernameProblemLanguageResultExecution timeMemory
730127welleythRestore Array (RMI19_restore)C++17
0 / 100
688 ms134124 KiB
#include <bits/stdc++.h> using namespace std; constexpr int M = 10000; constexpr int N = 5000; int n,m; int l[M],r[M],k[M],value[M]; int a[N]; int sumL[N][N]; int sumR[N][N]; int pref[N]; bool ok(bool t = false){ for(int i = 0; i < n; i++){ pref[i] = a[i]; if(i) pref[i] += pref[i-1]; } for(int i = 0; i < m; i++){ int S = pref[r[i]]; if(l[i]) S -= pref[l[i]-1]; if(S > sumR[l[i]][r[i]]) return false; if(t && S < sumL[l[i]][r[i]]) return false; } return true; } void solve(){ cin >> n >> m; for(int i = 0; i < m; i++){ cin >> l[i] >> r[i] >> k[i] >> value[i]; } for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ sumL[i][j] = 0; sumR[i][j] = j - i + 1; } } for(int i = 0; i < m; i++){ if(value[i] == 0) sumR[l[i]][r[i]] = min(sumR[l[i]][r[i]],r[i]-l[i]+1-k[i]); else sumL[l[i]][r[i]] = max(sumL[l[i]][r[i]],r[i]-l[i]+1-k[i]+1); } // for(int i = 0; i < m; i++){ // cout << sumL[l[i]][r[i]] << " " << sumR[l[i]][r[i]] << "\n"; // } for(int i = 0; i < n; i++){ a[i] = 1; if(ok()) continue; a[i] = 0; } assert(ok(true)); for(int i = 0; i < n; i++) cout << a[i] << " "; cout << "\n"; return; } signed main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int tests = 1; // cin >> tests; for(int test = 1; test <= tests; test++){ solve(); } return 0; } /** k-th [l..r] = value value == 0 -> cnt0 >= k value == 1 -> cnt0 < k cnt0 = (r - l + 1) - sum[l..r] = (r - l + 1) - cnt1 value == 0 cnt0 >= k (r - l + 1) - cnt1 >= k (r - l + 1) - k >= cnt1 cnt1 <= (r - l + 1) - k value == 1 cnt0 < k (r - l + 1) - cnt1 < k (r - l + 1) - k < cnt1 cnt1 > (r - l + 1) - k **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...