#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 time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
