結果
問題 | No.1920 Territory |
ユーザー |
👑 |
提出日時 | 2022-04-29 22:48:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 741 ms / 5,000 ms |
コード長 | 5,036 bytes |
コンパイル時間 | 1,596 ms |
コンパイル使用メモリ | 123,452 KB |
実行使用メモリ | 60,880 KB |
最終ジャッジ日時 | 2024-06-29 04:25:44 |
合計ジャッジ時間 | 13,735 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <cassert>#include <cmath>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <functional>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using Int = long long;template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }int uf[200'010];int root(int u) {return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));}bool connect(int u, int v) {u = root(u);v = root(v);if (u == v) return false;if (uf[u] > uf[v]) swap(u, v);uf[u] += uf[v];uf[v] = u;return true;}template <class T> void bAdd(vector<T> &bit, int pos, const T &val) {const int bitN = bit.size();for (int x = pos; x < bitN; x |= x + 1) bit[x] += val;}template <class T> T bSum(const vector<T> &bit, int pos) {T ret = 0;for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) ret += bit[x];return ret;}template <class T> T bSum(const vector<T> &bit, int pos0, int pos1) {return bSum(bit, pos1) - bSum(bit, pos0);}int M, N;vector<int> A, B, C;vector<int> P, Q, R;int main() {for (; ~scanf("%d%d", &M, &N); ) {A.resize(M);B.resize(M);C.resize(M);for (int i = 0; i < M; ++i) scanf("%d%d%d", &A[i], &B[i], &C[i]);P.resize(N);Q.resize(N);R.resize(N);for (int j = 0; j < N; ++j) scanf("%d%d%d", &P[j], &Q[j], &R[j]);int lim = 0;for (int i = 0; i < M; ++i) {chmax(lim, A[i]);chmax(lim, B[i]);chmax(lim, C[i]);}for (int j = 0; j < N; ++j) {chmax(lim, P[j]);chmax(lim, Q[j]);chmax(lim, R[j]);}lim += 5;Int numComps = 0;{int segN;for (segN = 1; segN < lim; segN <<= 1) {}vector<vector<int>> iss(segN << 1), jss(segN << 1);for (int i = 0; i < M; ++i) {// x \in [B[i], C[i]]int a = B[i], b = C[i] + 1;for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {if (a & 1) iss[a++].push_back(i);if (b & 1) iss[--b].push_back(i);}}for (int j = 0; j < N; ++j) {int a = P[j];for (a += segN; a; a >>= 1) {jss[a].push_back(j);}}fill(uf, uf + (M + N), -1);for (int a = 1; a < segN << 1; ++a) if (!iss[a].empty() && !jss[a].empty()) {// cerr<<"is = ";pv(iss[a].begin(),iss[a].end());// cerr<<"js = ";pv(jss[a].begin(),jss[a].end());vector<pair<pair<int, int>, int>> events;for (const int i : iss[a]) {events.emplace_back(make_pair(A[i], 1), i);}for (const int j : jss[a]) {events.emplace_back(make_pair(Q[j], 0), j);}sort(events.begin(), events.end());using Entry = pair<int, int>;priority_queue<Entry, vector<Entry>, greater<Entry>> que;for (const auto &e : events) {if (e.first.second) {const int i = e.second;for (; !que.empty() && que.top().first < A[i]; que.pop()) {}if (!que.empty()) {for (; ; ) {const auto p = que.top();que.pop();connect(i, M + p.second);if (que.empty()) {que.push(p);break;}}}} else {const int j = e.second;que.emplace(R[j], j);}}}for (int u = 0; u < M + N; ++u) if (uf[u] < 0) {++numComps;}}// cerr<<"uf = ";pv(uf,uf+(M+N));cerr<<"numComps = "<<numComps<<endl;Int numPoints = 0;{vector<vector<int>> adds(lim), rems(lim), jss(lim);for (int i = 0; i < M; ++i) {adds[B[i]].push_back(i);rems[C[i]].push_back(i);}for (int j = 0; j < N; ++j) {jss[P[j]].push_back(j);}vector<int> bit(lim, 0);for (int x = 0; x < lim; ++x) {for (const int i : adds[x]) {bAdd(bit, A[i], +1);}for (const int j : jss[x]) {Int num = 0;num += bSum(bit, R[j] + 1);num -= bSum(bit, Q[j]);numPoints += num;}for (const int i : rems[x]) {bAdd(bit, A[i], -1);}}}cerr<<"numPoints = "<<numPoints<<endl;Int ans = 0;ans += numPoints;ans -= (M + N);ans += numComps;printf("%lld\n", ans);}return 0;}