Submission #1228458

#TimeUsernameProblemLanguageResultExecution timeMemory
122845812345678Alternating Current (BOI18_alternating)C++17
52 / 100
191 ms19836 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5; int n, m, l[nx], r[nx], vs[nx], qs[nx], c[nx], vss[nx], f; vector<int> add[nx], rem[nx], d[nx]; set<int> cur; void dfs(int u) { vss[u]=1; for (auto v:d[u]) { if (vss[v]&&c[u]==c[v]) f=1; if (!vss[v]) c[v]=!c[u], dfs(v); } } struct segtree { int d[4*nx], lz[4*nx]; void pushlz(int l, int r, int i) { d[i]+=lz[i]; if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i]; lz[i]=0; } void update(int l, int r, int i, int ql, int qr, int vl) { pushlz(l, r, i); if (qr<l||r<ql) return; if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void(); int md=(l+r)/2; update(l, md, 2*i, ql, qr ,vl); update(md+1, r, 2*i+1, ql, qr ,vl); d[i]=min(d[2*i], d[2*i+1]); } int query(int l, int r, int i, int ql, int qr) { pushlz(l, r, i); if (qr<l||r<ql) return INT_MAX; if (ql<=l&&r<=qr) return d[i]; int md=(l+r)/2; return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr)); } } s; void addrange(int l, int r) { if (l<=r) s.update(1, n, 1, l, r, 1); else s.update(1, n, 1, 1, r, 1), s.update(1, n, 1, l, n, 1); } int getmin(int l, int r) { if (l<=r) return s.query(1, n, 1, l, r); else return min(s.query(1, n, 1, 1, r), s.query(1, n, 1, l, n)); } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=m; i++) { cin>>l[i]>>r[i]; if (l[i]<=r[i]) add[l[i]].push_back(i), rem[r[i]].push_back(i); else rem[r[i]].push_back(i), add[l[i]].push_back(i), cur.insert(i); } for (int i=1; i<=n; i++) { qs[i]+=qs[i-1]; for (auto x:add[i]) cur.insert(x); if (cur.size()<2) return cout<<"impossible", 0; if (cur.size()==2) { int u=*cur.begin(), v=*next(cur.begin()); d[u].push_back(v); d[v].push_back(u); vs[u]=vs[v]=1; } for (auto x:rem[i]) cur.erase(x); } for (int i=1; i<=m; i++) if (vs[i]) dfs(i); if (f) return cout<<"impossible", 0; for (int i=1; i<=m; i++) if (c[i]) addrange(l[i], r[i]); for (int i=1; i<=m; i++) { if (!vs[i]) if (getmin(l[i], r[i])==0) addrange(l[i], r[i]), c[i]=1; //cout<<i<<' '<<c[i]<<' '<<vs[i]<<'\n'; cout<<c[i]; } }
#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...