제출 #710956

#제출 시각아이디문제언어결과실행 시간메모리
710956Sanzhar23Restore Array (RMI19_restore)C++14
13 / 100
8 ms1116 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define bug cout << "bug" << endl #define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define all(x) x.begin(), x.end() #define F first #define S second #define pll pair <ll, ll> #define pii pair <int, int> #define triple pair <pair <ll, ll> , ll> #define ull unsigned long long #define ld long double #define pinode pair <node*, node*> const ll INF = 9e18 + 5; const ll inf = 1e9 + 5; const ll N = 1e4 + 5; const ll shift = 2e6; const ll mod = 998244353; const ll mod2 = 1e9 + 9; const ll M = 1e3 + 5; const ll LOG = 21; const ll sp = 263; const ll sp2 = 9973; const int block = 100; const double eps = 1e-10; int n, m, l[N], r[N], k[N], val[N], a[N], pref[N], ones[N], zeros[N], pref1[N], pref2[N]; int sb2 = 1, can = 1, sb3 = 1; struct BIT{ int t[N]; void upd(int pos, int val){ while(pos <= N - 5){ t[pos] += val; pos = (pos | (pos + 1)); } } int sum(int pos){ int res = 0; while(pos >= 0){ res += t[pos]; pos = (pos & (pos + 1)) - 1; } return res; } int get(int l, int r){ return sum(r) - sum(l - 1); } } tr1, tr2; int main(){ speed; cin >> n >> m; for(int i = 1; i <= m; i++){ cin >> l[i] >> r[i] >> k[i] >> val[i]; l[i]++; r[i]++; if(k[i] != 1) sb2 = 0; if(k[i] != r[i] - l[i] + 1 && k[i] != 1) sb3 = 0; } if(sb2 || sb3){ for(int i = 1; i <= m; i++){ if(val[i] == 0 && k[i] == r[i] - l[i] + 1){ zeros[l[i]] += 1; zeros[r[i] + 1] -= 1; } if(val[i] == 1 && k[i] == 1){ ones[l[i]] += 1; ones[r[i] + 1] -= 1; } } for(int i = 1; i <= n; i++){ zeros[i] += zeros[i - 1]; ones[i] += ones[i - 1]; } for(int i = 1; i <= n; i++){ zeros[i] = min(zeros[i], 1); ones[i] = min(ones[i], 1); tr1.upd(i, zeros[i]); tr2.upd(i, ones[i]); if(zeros[i] == 1 && ones[i] == 1) can = 0; } if(!can){ cout << -1 << endl; return 0; } /* for(int i = 1; i <= n; i++){ if(zeros[i]) cout << 0 << " "; else if(ones[i]) cout << 1 << " "; else cout << -1 << " "; } cout << endl << endl; */ vector <int> vt[N]; for(int i = 1; i <= m; i++){ if(val[i] == 0 && k[i] == r[i] - l[i] + 1) continue; if(val[i] == 1 && k[i] == 1) continue; if(val[i] == 0 && k[i] == 1){ if(tr1.get(l[i], r[i]) > 0) continue; } if(val[i] == 1 && k[i] == r[i] - l[i] + 1){ if(tr2.get(l[i], r[i]) > 0) continue; } vt[l[i]].pb(i); } set <pii> st; for(int i = 1; i <= n; i++){ while(st.size()){ int idx = (st.begin() -> second); if(val[idx] == 1){ if(tr2.get(l[i], r[i]) > 0){ st.erase(st.begin()); continue; } }else{ if(tr1.get(l[i], r[i]) > 0){ st.erase(st.begin()); continue; } } break; } for(auto to : vt[i]){ st.insert({r[to], to}); } if(st.size() && (st.begin() -> first) < i){ can = 0; // cout << "IDX : " << (st.begin() -> first) << endl; // return 0; break; } if(zeros[i] == 0 && ones[i] == 0 && st.size()){ int idx = (st.begin() -> second); st.erase(st.begin()); if(val[idx] == 0){ zeros[i] = 1; tr1.upd(i, zeros[i]); } else{ ones[i] = 1; tr2.upd(i, ones[i]); } } while(st.size()){ int idx = (st.begin() -> second); if(val[idx] == 1){ if(tr2.get(l[i], r[i]) > 0){ st.erase(st.begin()); continue; } }else{ if(tr1.get(l[i], r[i]) > 0){ st.erase(st.begin()); continue; } } break; } } // return 0; // cout << "Q Q Q" << endl; // for(auto to : st){ // cout << to.F << " " << to.S << endl; // } // return 0; if(st.size() || !can){ cout << -1 << endl; return 0; } for(int i = 1; i <= n; i++){ if(ones[i]) cout << 1 << " "; else if(zeros[i]) cout << 0 << " "; else cout << 0 << " "; } } } /* %I64d6 7 7 0 2 1 0 0 6 1 0 0 1 1 0 1 1 1 1 6 6 1 1 3 6 1 1 2 4 1 1 0 1 1 1 1 1 1 %I64d */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...