#748139 (C++17(clang)) No.1920 Territory

提出ソース

結果

問題	No.1920 Territory
ユーザー	るさ
提出日時	2022-03-25 14:10:56
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	377 ms / 5,000 ms
コード長	11,693 bytes
コンパイル時間	3,863 ms
コンパイル使用メモリ	363,760 KB
実行使用メモリ	22,704 KB
最終ジャッジ日時	2023-09-11 01:20:42
合計ジャッジ時間	11,632 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 10,472 KB
testcase_01	AC	5 ms 8,444 KB
testcase_02	AC	5 ms 8,416 KB
testcase_03	AC	10 ms 10,404 KB
testcase_04	AC	10 ms 10,404 KB
testcase_05	AC	11 ms 10,476 KB
testcase_06	AC	10 ms 10,384 KB
testcase_07	AC	10 ms 10,388 KB
testcase_08	AC	10 ms 10,440 KB
testcase_09	AC	10 ms 10,444 KB
testcase_10	AC	10 ms 10,480 KB
testcase_11	AC	10 ms 10,448 KB
testcase_12	AC	9 ms 10,380 KB
testcase_13	AC	377 ms 16,036 KB
testcase_14	AC	372 ms 15,476 KB
testcase_15	AC	376 ms 15,144 KB
testcase_16	AC	370 ms 15,428 KB
testcase_17	AC	367 ms 15,132 KB
testcase_18	AC	360 ms 16,032 KB
testcase_19	AC	354 ms 15,796 KB
testcase_20	AC	360 ms 16,548 KB
testcase_21	AC	358 ms 14,908 KB
testcase_22	AC	350 ms 15,412 KB
testcase_23	AC	198 ms 22,704 KB
testcase_24	AC	274 ms 22,288 KB
testcase_25	AC	117 ms 13,848 KB
testcase_26	AC	117 ms 13,232 KB
testcase_27	AC	116 ms 12,492 KB
testcase_28	AC	116 ms 13,288 KB
testcase_29	AC	268 ms 22,048 KB
testcase_30	AC	266 ms 22,456 KB
testcase_31	AC	315 ms 17,724 KB
testcase_32	AC	316 ms 17,540 KB
testcase_33	AC	161 ms 15,216 KB
testcase_34	AC	160 ms 15,620 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MAX_N (ll)110000
#define MAX_POS (ll)660000
#define INFTY (ll)1000000000000000000
#define MOD (ll)998244353
#define ZERO (ll)0

#define iscan(x) scanf("%d", &x)
#define llscan(x) scanf("%lld", &x)
#define isarray(ar, ln) for(ll scani=0; scani<ln; scani++){scanf("%d", ar+scani);}
#define llsarray(ar, ln) for(ll scani=0; scani<ln; scani++){scanf("%lld", ar+scani);}
#define sarray(tp, ar, ln) for(ll scani=0; scani<ln; scani++){scanf(tp, ar+scani);}

#define iprint(x) printf("%d\n", x)
#define llprint(x) printf("%lld\n", x)
#define iprintwo(x) printf("%d", x)
#define llprintwo(x) printf("%lld", x)
#define iparray(ar, ln) for(ll scani=0; scani<ln; scani++){printf("%d\n", ar[scani]);}
#define llparray(ar, ln) for(ll scani=0; scani<ln; scani++){printf("%lld\n", ar[scani]);}
#define iparrayspace(ar, ln) for(ll scani=0; scani<ln-1; scani++){printf("%d ", ar[scani]);};printf("%d\n", ar[ln-1]);
#define llparrayspace(ar, ln) for(ll scani=0; scani<ln-1; scani++){printf("%lld ", ar[scani]);};printf("%lld\n", ar[ln-1]);

#define range(i, ln) (ll i=0; i<ln; i++)
#define range2(i, st, ed) (ll i=st; i<ed; i++)
#define range3(i, st, ed, stp) (ll i=st; i<ed; i+=stp)

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}

template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;

  public:
    fenwick_tree() : _n(0) {}
    fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

  private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};


int main() {
  
  int n,m;
  iscan(n); iscan(m);
  static int xbegin[MAX_N], xend[MAX_N], ybegin[MAX_N], yend[MAX_N];
  int a, b, c, fi, se, v, w, pmin, pmax;
  static pair<int, int> query[MAX_POS];
  
  for range(i, n) {
    iscan(a); iscan(b); iscan(c);
    xbegin[i] = a;
    xend[i]   = a;
    query[i*2] = {b*3-1, i};
    query[i*2+1] = {c*3+1, i};
  }
  
  for range(i, m) {
    iscan(a); iscan(b); iscan(c);
    ybegin[i] = b;
    yend[i]   = c;
    query[2*n+i] = {a*3, i};
  }
  
  sort(query, query+(2*n+m));
  
  int line_cnt = n+m;
  long long intersects=0, connected_cnt=0;
  
  static dsu uf(MAX_POS);
  set<int> set_t;
  set<pair<int, int>> set_s;
  
  fenwick_tree<int> bit(MAX_POS);
  for range(q, 2*n+m) {
    fi = query[q].first; se = query[q].second;
    switch (fi % 3) {
      case 2:
        bit.add(xbegin[se], 1);
        break;
      case 0:
        intersects += bit.sum(ybegin[se], yend[se]+1);
        break;
      case 1:
        bit.add(xend[se], -1);
    }
  }
  set<pair<int, int>>::iterator sec;
  set<int>::iterator lb;
  pair<int, int> p1, p2;
  for range(q, 2*n+m) {
    fi = query[q].first; se = query[q].second;
    switch (fi % 3) {
      case 2:
        v = xbegin[se];
        set_t.insert(v);
        sec = set_s.lower_bound({v, v});
        if (sec != set_s.begin()) {
          sec--;
          if ((*sec).second > v) {
            lb = set_t.lower_bound(v);
            p1 = {*++lb, (*sec).second};
            lb--; lb--;
            p2 = {(*sec).first, *lb};
            set_s.erase(sec);
            
            set_s.insert(p1);
            // printf("case 2: add back %d %d in query %lld\n", p1.first, p1.second, q);
            set_s.insert(p2);
            // printf("case 2: add front %d %d in query %lld\n", p2.first, p2.second, q);
          }
        }
        set_s.insert(make_pair(v, v));
        // printf("case 2: add itself %d %d in query %lld\n", v, v, q);
        break;
      case 0:
        v = ybegin[se]; w = yend[se];
        lb = set_t.lower_bound(v);
        if (lb == set_t.end() || *lb > w) {
          connected_cnt++;
          // printf("case 0: dont merge in query %lld\n", q);
          break;
        }
        for (sec = set_s.begin(); sec != set_s.end(); sec++) {
          // printf("case 0: segment list %d %d in query %lld\n", (*sec).first, (*sec).second, q);
        }
        sec = set_s.lower_bound({v, 0});
        if (sec != set_s.begin() && (*--sec).second < v) sec++;
        pmin = (*sec).first;
        while (sec != set_s.end() && (*sec).first <= w) {
          pmax = (*sec).second;
          uf.merge(pmin, (*sec).first);
          // printf("case 0: merge %d %d in query %lld\n", pmin, (*sec).first, q);
          // printf("case 0: erase %d %d in query %lld\n", (*sec).first, (*sec).second, q);
          set_s.erase(sec++);
        }
        set_s.insert({pmin, pmax});
        // printf("case 0: merge segment into %d %d in query %lld\n", pmin, pmax, q);
        break;
      case 1:
        v = xend[se];
        set_t.erase(v);
        sec = set_s.lower_bound({v, 10000000});
        sec--;
        if (v == (*sec).first) {
          if (v == (*sec).second) {
            set_s.erase(sec);
            // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q);
            break;
          }
          lb = set_t.lower_bound(v);
          p1 = {*lb, (*sec).second};
          set_s.erase(sec);
          // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q);
          set_s.insert(p1);
          // printf("case 1: add back %d %d in query %lld\n", p1.first, p1.second, q);
        } else if (v == (*sec).second) {
          lb = set_t.lower_bound(v);
          p2 = {(*sec).first, *--lb};
          set_s.erase(sec);
          // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q);
          set_s.insert(p2);
          // printf("case 1: add front %d %d in query %lld\n", p2.first, p2.second, q);
        } else {
          lb = set_t.lower_bound(v);
          p1 = {*lb, (*sec).second};
          p2 = {(*sec).first, *--lb};
          set_s.erase(sec);
          // printf("case 1: erase segment %d %d in query %lld\n", (*sec).first, (*sec).second, q);
          set_s.insert(p1);
          // printf("case 1: add back %d %d in query %lld\n", p1.first, p1.second, q);
          set_s.insert(p2);
          // printf("case 1: add front %d %d in query %lld\n", p2.first, p2.second, q);
        }
    }
  }
  
  set<int> used;
  for range(i, n) {
    int l = uf.leader(xbegin[i]);
    if (used.find(l) == used.end()) {
      connected_cnt++;
      used.insert(l);
      // iprint(l);
    }
  }
  // iprint(line_cnt);
  // iprint(intersects);
  // iprint(connected_cnt);
  llprint(connected_cnt + intersects - line_cnt);
  
  
}

yukicoder

結果

テストケース

ソースコード