답안 #798471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798471 2023-07-30T18:14:01 Z cig32 Usmjeravanje (COCI22_usmjeravanje) C++17
0 / 110
1 ms 340 KB
#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);
}
// 勿忘初衷
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -