結果
| 問題 |
No.1920 Territory
|
| コンテスト | |
| ユーザー |
 るさ
|
| 提出日時 | 2022-03-25 13:52:58 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 11,684 bytes |
| コンパイル時間 | 10,028 ms |
| コンパイル使用メモリ | 390,028 KB |
| 実行使用メモリ | 19,840 KB |
| 最終ジャッジ日時 | 2024-06-28 15:50:19 |
| 合計ジャッジ時間 | 14,272 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 WA * 3 RE * 16 |
ソースコード
#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;
int 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_N);
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);
iprint(connected_cnt + intersects - line_cnt);
}