Submission #798470

#TimeUsernameProblemLanguageResultExecution timeMemory
798470cig32Usmjeravanje (COCI22_usmjeravanje)C++17
0 / 110
1 ms340 KiB
#include "bits/stdc++.h" using namespace std; #define int long long const int MAXN = 4e5 + 10; const int MOD = 1e9 + 7; mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } int bm(int b, int p) { if(p==0) return 1 % MOD; int r = bm(b, p >> 1); if(p&1) return (((r*r) % MOD) * b) % MOD; return (r*r) % MOD; } int inv(int b) { return bm(b, MOD-2); } int fastlog(int x) { return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1); } void printcase(int i) { cout << "Case #" << i << ": "; } struct segtree_basic { struct node { int lazyval, mi, ma, sum; char lazytag; int len; // not changing }; int stok; vector<node> st; void bu(int l, int r, int idx) { st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0; st[idx].lazytag = '?'; st[idx].len = r - l + 1; if(l == r) { return; } int mid = (l + r) >> 1; bu(l, mid, 2*idx+1); bu(mid+1, r, 2*idx+2); } void push_down(int idx) { if(st[idx].lazytag == '?') return; if(st[idx].lazytag == ':') { st[2*idx+1].lazyval = st[idx].lazyval; st[2*idx+1].mi = st[idx].lazyval; st[2*idx+1].ma = st[idx].lazyval; st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len; st[2*idx+1].lazytag = ':'; st[2*idx+2].lazyval = st[idx].lazyval; st[2*idx+2].mi = st[idx].lazyval; st[2*idx+2].ma = st[idx].lazyval; st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len; st[2*idx+2].lazytag = ':'; } else { st[2*idx+1].lazyval += st[idx].lazyval; st[2*idx+1].mi += st[idx].lazyval; st[2*idx+1].ma += st[idx].lazyval; st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len; st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+'); st[2*idx+2].lazyval += st[idx].lazyval; st[2*idx+2].mi += st[idx].lazyval; st[2*idx+2].ma += st[idx].lazyval; st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len; st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+'); } st[idx].lazytag = '?'; st[idx].lazyval = 0; } void push_up(int idx) { st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi); st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma); st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum; } void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v if(l <= constl && constr <= r) { st[idx].lazyval = val; st[idx].mi = val; st[idx].ma = val; st[idx].sum = val * st[idx].len; st[idx].lazytag = ':'; return; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val); else { u1(l, r, constl, mid, 2*idx+1, val); u1(l, r, mid+1, constr, 2*idx+2, val); } push_up(idx); } void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v if(l <= constl && constr <= r) { st[idx].lazyval += val; st[idx].mi += val; st[idx].ma += val; st[idx].sum += val * st[idx].len; st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+'); return; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val); else { u2(l, r, constl, mid, 2*idx+1, val); u2(l, r, mid+1, constr, 2*idx+2, val); } push_up(idx); } int qu1(int l, int r, int constl, int constr, int idx) { // range min if(l <= constl && constr <= r) return st[idx].mi; int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2); else if(constr < l || r < mid + 1) return qu1(l, r, constl, mid, 2*idx+1); else { return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2)); } } int qu2(int l, int r, int constl, int constr, int idx) { // range max if(l <= constl && constr <= r) return st[idx].ma; int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2); else if(constr < l || r < mid + 1) return qu2(l, r, constl, mid, 2*idx+1); else { return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2)); } } int qu3(int l, int r, int constl, int constr, int idx) { // range sum if(l <= constl && constr <= r) return st[idx].sum; int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu3(l, r, mid+1, constr, 2*idx+2); else if(constr < l || r < mid + 1) return qu3(l, r, constl, mid, 2*idx+1); else { return qu3(l, r, constl, mid, 2*idx+1) + qu3(l, r, mid+1, constr, 2*idx+2); } } int qu4(int l, int r, int constl, int constr, int idx, int val) { // first at least v if(l <= constl && constr <= r) { if(st[idx].ma < val) return -1; while(constl < constr) { int mid = (constl + constr) >> 1; push_down(idx); if(st[2*idx+1].ma >= val) constr = mid, idx = 2*idx + 1; else constl = mid+1, idx = 2*idx + 2; } return constl; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu4(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid + 1) return qu4(l, r, constl, mid, 2*idx+1, val); else { int lchild = qu4(l, r, constl, mid, 2*idx+1, val); if(lchild != -1) return lchild; return qu4(l, r, mid+1, constr, 2*idx+2, val); } } int qu5(int l, int r, int constl, int constr, int idx, int val) { // first at most v if(l <= constl && constr <= r) { if(st[idx].mi > val) return -1; while(constl < constr) { int mid = (constl + constr) >> 1; push_down(idx); if(st[2*idx+1].mi <= val) constr = mid, idx = 2*idx + 1; else constl = mid+1, idx = 2*idx + 2; } return constl; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu5(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid + 1) return qu5(l, r, constl, mid, 2*idx+1, val); else { int lchild = qu5(l, r, constl, mid, 2*idx+1, val); if(lchild != -1) return lchild; return qu5(l, r, mid+1, constr, 2*idx+2, val); } } int qu6(int l, int r, int constl, int constr, int idx, int val) { // last at least v if(l <= constl && constr <= r) { if(st[idx].ma < val) return -1; while(constl < constr) { int mid = (constl + constr) >> 1; push_down(idx); if(st[2*idx+2].ma >= val) constl = mid+1, idx = 2*idx + 2; else constr = mid, idx = 2*idx + 1; } return constl; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu6(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid + 1) return qu6(l, r, constl, mid, 2*idx+1, val); else { int rchild = qu6(l, r, mid+1, constr, 2*idx+2, val); if(rchild != -1) return rchild; return qu6(l, r, constl, mid, 2*idx+1, val); } } int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v if(l <= constl && constr <= r) { if(st[idx].mi > val) return -1; while(constl < constr) { int mid = (constl + constr) >> 1; push_down(idx); if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2; else constr = mid, idx = 2*idx + 1; } return constl; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val); else { int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val); if(rchild != -1) return rchild; return qu7(l, r, constl, mid, 2*idx+1, val); } } int qu8(int l, int r, int constl, int constr, int idx, int val) { // first partial sum at least v, only works when partial sum is non-decreasing if(l <= constl && constr <= r) { if(st[idx].sum < val) return -1; while(constl < constr) { int mid = (constl + constr) >> 1; push_down(idx); if(st[2*idx+1].sum >= val) { idx = 2*idx+1, constr = mid; } else { val -= st[2*idx+1].sum; idx = 2*idx+2, constl = mid+1; } } return constl; } int mid = (constl + constr) >> 1; push_down(idx); if(mid < l || r < constl) return qu8(l, r, mid+1, constr, 2*idx+2, val - st[2*idx+1].sum); else if(constr < l || r < mid+1) return qu8(l, r, constl, mid, 2*idx+1, val); else { int lchild = qu8(l, r, constl, mid, 2*idx+1, val); if(lchild != -1) return lchild; return qu8(l, r, mid+1, constr, 2*idx+2, val - st[2*idx+1].sum); } } public: void resize(int k) { st.resize(4*k + 10); stok = k; bu(0, k, 0); } void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); } void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); } int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); } int query_max(int l, int r) { return qu2(l, r, 0, stok, 0); } int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); } int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); } int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); } int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); } int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); } int query_firstPSAtLeast(int l, int r, int v) { return qu8(l, r, 0, stok, 0, v); } }; int a, b, m; segtree_basic stmin, stmax; int dsu[MAXN]; int sz[MAXN]; struct info { int la = -1, ra = -1; int lb = -1, rb = -1; } component[MAXN]; int x[MAXN], y[MAXN], dir[MAXN]; set<int> asets, bsets; int set_of(int u) { if(dsu[u] == u) return u; return dsu[u] = set_of(dsu[u]); } void Union(int u, int v) { u = set_of(u), v = set_of(v); info iu = component[u], iv = component[v]; int la = min(iu.la == -1 ? 1e9 : iu.la, iv.la == -1 ? 1e9 : iv.la); int ra = max(iu.ra, iv.ra); int lb = min(iu.lb == -1 ? 1e9 : iu.lb, iv.lb == -1 ? 1e9 : iv.lb); int rb = max(iu.rb, iv.rb); dsu[set_of(u)] = set_of(v); auto it = asets.lower_bound(la); vector<int>del; while(it != asets.end() && (*it) < ra) { int w = *it; del.push_back(w); dsu[set_of(w)] = set_of(w+1); it++; } for(int x: del) asets.erase(x); del.clear(); it = bsets.lower_bound(lb); while(it != bsets.end() && (*it) < rb) { int w = *it; del.push_back(w); dsu[set_of(w)] = set_of(w+1); it++; } for(int x: del) bsets.erase(x); del.clear(); component[set_of(u)] = {la, ra, lb, rb}; stmin.range_assign(la, ra, lb); stmax.range_assign(la, ra, rb); } int save[MAXN]; void insert_connection(int idx) { y[idx] += a; if(set_of(x[idx]) == set_of(y[idx])) return; if(component[set_of(x[idx])].lb != -1 && component[set_of(y[idx])].la != -1) { // both are in scc if(component[set_of(x[idx])].la < component[set_of(y[idx])].la) dir[idx] = 1; else dir[idx] = 0; Union(x[idx], y[idx]); } else if(component[set_of(x[idx])].lb != -1) { if(component[set_of(x[idx])].lb < component[set_of(y[idx])].lb) dir[idx] = 1; else dir[idx] = 0; Union(x[idx], y[idx]); } else if(component[set_of(y[idx])].la != -1) { if(component[set_of(x[idx])].la < component[set_of(y[idx])].la) dir[idx] = 1; else dir[idx] = 0; Union(x[idx], y[idx]); } else { cout << idx << " oh no" << endl; if(stmax.query_max(1, x[idx]) >= y[idx]) { dir[idx] = 0; int mm = stmax.query_max(1, x[idx]); int id = stmax.query_firstAtLeast(1, x[idx], y[idx]); stmax.range_assign(id, x[idx], 0); stmin.range_assign(id, x[idx], a+b+1); for(int i=id; i<x[idx]; i++) { dir[save[i]] = 1; dsu[set_of(i)]=set_of(i+1); } component[set_of(x[idx])] = {id, x[idx], -1, -1}; for(int i=y[idx]; i<mm; i++) { dsu[set_of(i)]=set_of(i+1); } component[set_of(y[idx])] = {-1, -1, y[idx], mm}; Union(x[idx], y[idx]); //cout << component[set_of(x[idx])].la << ' ' << component[set_of(x[idx])].ra << ' '; //cout << component[set_of(x[idx])].lb << ' ' << component[set_of(x[idx])].rb << '\n'; } else if(stmin.query_min(x[idx], a) <= y[idx]) { dir[idx] = 1; int mm = stmin.query_max(x[idx], a); int id = stmin.query_lastAtMost(x[idx], a, y[idx]); stmax.range_assign(x[idx], id, 0); stmin.range_assign(x[idx], id, a+b+1); for(int i=id; i>x[idx]; i--) { dir[save[i]] = 1; dsu[set_of(i)]=set_of(i-1); } component[set_of(x[idx])] = {x[idx], id, -1, -1}; for(int i=y[idx]; i>mm; i--) { dsu[set_of(i)]=set_of(i-1); } component[set_of(y[idx])] = {-1, -1, mm, y[idx]}; Union(x[idx], y[idx]); } else { save[x[idx]]=idx; stmin.range_assign(x[idx],x[idx],y[idx]); stmax.range_assign(x[idx],x[idx],y[idx]); } } } void solve(int tc) { cin >> a >> b >> m; stmin.resize(a); stmax.resize(a); stmin.range_assign(1, a, a+b+1); for(int i=1; i<a; i++) asets.insert(i); for(int i=a+1; i<a+b; i++) bsets.insert(i); for(int i=1; i<=a+b; i++) dsu[i] = i, sz[i] = 1; for(int i=1; i<=a; i++) component[i].la = component[i].ra = i; for(int i=a+1; i<=a+b; i++) component[i].lb = component[i].rb = i; for(int i=1; i<=m; i++) { cin >> x[i] >> y[i]; insert_connection(i); } set<int>st; for(int i=1;i<=a+b;i++)st.insert(set_of(i)); cout<<st.size()<<"\n"; for(int i=1;i<=m;i++)cout<<dir[i]<<" "; cout<<"\n"; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) solve(i); } // 勿忘初衷
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...