Submission #13336903


Source Code Expand

Copy
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

const int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

const int N = 3e3 + 10;
bool visit[N][N];
bitset<4> dir[N][N];

struct Seg {
  int L, R, pos;
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<Seg> a(n), b(m);
  vector<int> X, Y;
  X.push_back(-INF); X.push_back(INF);
  Y.push_back(-INF); Y.push_back(INF);
  for (int i = 0; i < n; ++i) {
    cin >> a[i].L >> a[i].R >> a[i].pos;
    X.push_back(a[i].L);
    X.push_back(a[i].R);
    Y.push_back(a[i].pos);
  }
  for (int i = 0; i < m; ++i) {
    cin >> b[i].pos >> b[i].L >> b[i].R;
    Y.push_back(b[i].L);
    Y.push_back(b[i].R);
    X.push_back(b[i].pos);
  }
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  sort(Y.begin(), Y.end());
  Y.erase(unique(Y.begin(), Y.end()), Y.end());

  int sx = upper_bound(X.begin(), X.end(), 0) - X.begin() - 1;
  int sy = upper_bound(Y.begin(), Y.end(), 0) - Y.begin() - 1;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int k = 0; k < 4; ++k) dir[i][j][k] = 1;
    }
  }

  for (int i = 0; i < n; ++i) {
    int u = lower_bound(X.begin(), X.end(), a[i].L) - X.begin();
    int v = lower_bound(X.begin(), X.end(), a[i].R) - X.begin();
    int w = lower_bound(Y.begin(), Y.end(), a[i].pos) - Y.begin();
    for (int x = u; x < v; ++x) {
      dir[x][w - 1][1] = dir[x][w][3] = 0;
    }
  }
  for (int i = 0; i < m; ++i) {
    int u = lower_bound(Y.begin(), Y.end(), b[i].L) - Y.begin();
    int v = lower_bound(Y.begin(), Y.end(), b[i].R) - Y.begin();
    int w = lower_bound(X.begin(), X.end(), b[i].pos) - X.begin();
    for (int y = u; y < v; ++y) {
      dir[w - 1][y][0] = dir[w][y][2] = 0;
    }
  }
  int64 ret = 0;
  queue<ii> Q;
  Q.push({sx, sy});
  visit[sx][sy] = true;
  bool found = false;
  while (!Q.empty()) {
    int u = Q.front().first;
    int v = Q.front().second;
    // trace(u, v, X[u], X[u + 1], Y[v], Y[v + 1]);
    Q.pop();
    ret += 1LL * (X[u + 1] - X[u]) * (Y[v + 1] - Y[v]);
    for (int k = 0; k < 4; ++k) {
      if (!dir[u][v][k]) continue;
      int nu = u + d[k][0];
      int nv = v + d[k][1];
      if (nu < 0 || nu == X.size() - 1 || nv < 0 || nv >= Y.size() - 1) continue;
      if (nu == 0 || nv == 0 || nu == X.size() - 2 || nv == Y.size() - 2) found = true;
      if (visit[nu][nv]) continue;
      visit[nu][nv] = true;
      Q.push({nu, nv});
    }
  }
  if (found) {
    cout << "INF" << endl;
  } else {
    cout << ret << endl;
  }
  return 0;
}

Submission Info

Submission Time
Task F - . (Single Dot)
User cuiaoxiang
Language C++ (Clang 10.0.0)
Score 600
Code Size 4995 Byte
Status AC
Exec Time 315 ms
Memory 82848 KB

Compile Error

./Main.cpp:78:11: warning: unused variable 'MOD' [-Wunused-const-variable]
const int MOD = 1e9 + 7;
          ^
1 warning generated.

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 96
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt, sub1_36.txt, sub1_37.txt, sub1_38.txt, sub1_39.txt, sub1_40.txt, sub1_41.txt, sub1_42.txt, sub1_43.txt, sub1_44.txt, sub1_45.txt, sub1_46.txt, sub1_47.txt, sub1_48.txt, sub1_49.txt, sub1_50.txt, sub1_51.txt, sub1_52.txt, sub1_53.txt, sub1_54.txt, sub1_55.txt, sub1_56.txt, sub1_57.txt, sub1_58.txt, sub1_59.txt, sub1_60.txt, sub1_61.txt, sub1_62.txt, sub1_63.txt, sub1_64.txt, sub1_65.txt, sub1_66.txt, sub1_67.txt, sub1_68.txt, sub1_69.txt, sub1_70.txt, sub1_71.txt, sub1_72.txt, sub1_73.txt, sub1_74.txt, sub1_75.txt, sub1_76.txt, sub1_77.txt, sub1_78.txt, sub1_79.txt, sub1_80.txt, sub1_81.txt, sub1_82.txt, sub1_83.txt, sub1_84.txt, sub1_85.txt, sub1_86.txt, sub1_87.txt, sub1_88.txt, sub1_89.txt, sub1_90.txt, sub1_91.txt, sub1_92.txt, sub1_93.txt, sub1_94.txt
Case Name Status Exec Time Memory
sample_01.txt AC 56 ms 73876 KB
sample_02.txt AC 58 ms 73844 KB
sub1_01.txt AC 60 ms 74040 KB
sub1_02.txt AC 60 ms 74336 KB
sub1_03.txt AC 58 ms 74032 KB
sub1_04.txt AC 55 ms 74200 KB
sub1_05.txt AC 66 ms 74284 KB
sub1_06.txt AC 57 ms 74040 KB
sub1_07.txt AC 58 ms 73956 KB
sub1_08.txt AC 62 ms 76208 KB
sub1_09.txt AC 61 ms 74028 KB
sub1_10.txt AC 71 ms 73992 KB
sub1_11.txt AC 54 ms 73884 KB
sub1_12.txt AC 56 ms 73856 KB
sub1_13.txt AC 54 ms 73852 KB
sub1_14.txt AC 54 ms 73984 KB
sub1_15.txt AC 57 ms 74000 KB
sub1_16.txt AC 53 ms 73852 KB
sub1_17.txt AC 57 ms 74072 KB
sub1_18.txt AC 78 ms 77008 KB
sub1_19.txt AC 79 ms 76972 KB
sub1_20.txt AC 78 ms 76920 KB
sub1_21.txt AC 78 ms 76856 KB
sub1_22.txt AC 70 ms 76860 KB
sub1_23.txt AC 76 ms 76920 KB
sub1_24.txt AC 72 ms 76916 KB
sub1_25.txt AC 77 ms 76856 KB
sub1_26.txt AC 77 ms 76824 KB
sub1_27.txt AC 62 ms 74688 KB
sub1_28.txt AC 61 ms 74856 KB
sub1_29.txt AC 58 ms 74164 KB
sub1_30.txt AC 62 ms 74460 KB
sub1_31.txt AC 58 ms 73896 KB
sub1_32.txt AC 75 ms 76832 KB
sub1_33.txt AC 62 ms 74720 KB
sub1_34.txt AC 64 ms 74816 KB
sub1_35.txt AC 69 ms 76304 KB
sub1_36.txt AC 65 ms 74676 KB
sub1_37.txt AC 74 ms 76844 KB
sub1_38.txt AC 57 ms 74688 KB
sub1_39.txt AC 54 ms 74456 KB
sub1_40.txt AC 76 ms 76872 KB
sub1_41.txt AC 55 ms 74640 KB
sub1_42.txt AC 54 ms 74024 KB
sub1_43.txt AC 56 ms 74048 KB
sub1_44.txt AC 53 ms 73900 KB
sub1_45.txt AC 53 ms 74056 KB
sub1_46.txt AC 54 ms 73904 KB
sub1_47.txt AC 60 ms 75608 KB
sub1_48.txt AC 59 ms 75592 KB
sub1_49.txt AC 62 ms 75652 KB
sub1_50.txt AC 60 ms 75624 KB
sub1_51.txt AC 64 ms 75624 KB
sub1_52.txt AC 65 ms 75628 KB
sub1_53.txt AC 61 ms 75616 KB
sub1_54.txt AC 62 ms 75736 KB
sub1_55.txt AC 199 ms 82792 KB
sub1_56.txt AC 184 ms 82848 KB
sub1_57.txt AC 224 ms 82728 KB
sub1_58.txt AC 174 ms 82828 KB
sub1_59.txt AC 175 ms 82728 KB
sub1_60.txt AC 210 ms 82724 KB
sub1_61.txt AC 100 ms 78988 KB
sub1_62.txt AC 175 ms 82672 KB
sub1_63.txt AC 54 ms 74436 KB
sub1_64.txt AC 155 ms 81248 KB
sub1_65.txt AC 58 ms 75132 KB
sub1_66.txt AC 66 ms 76120 KB
sub1_67.txt AC 54 ms 74520 KB
sub1_68.txt AC 61 ms 75112 KB
sub1_69.txt AC 61 ms 75248 KB
sub1_70.txt AC 60 ms 75264 KB
sub1_71.txt AC 54 ms 73832 KB
sub1_72.txt AC 53 ms 73840 KB
sub1_73.txt AC 53 ms 73912 KB
sub1_74.txt AC 74 ms 74044 KB
sub1_75.txt AC 56 ms 73832 KB
sub1_76.txt AC 91 ms 74044 KB
sub1_77.txt AC 56 ms 74780 KB
sub1_78.txt AC 57 ms 74920 KB
sub1_79.txt AC 56 ms 75792 KB
sub1_80.txt AC 56 ms 75804 KB
sub1_81.txt AC 59 ms 75760 KB
sub1_82.txt AC 60 ms 76624 KB
sub1_83.txt AC 53 ms 74016 KB
sub1_84.txt AC 58 ms 74024 KB
sub1_85.txt AC 56 ms 73908 KB
sub1_86.txt AC 53 ms 73852 KB
sub1_87.txt AC 55 ms 73868 KB
sub1_88.txt AC 53 ms 73736 KB
sub1_89.txt AC 313 ms 82824 KB
sub1_90.txt AC 315 ms 82748 KB
sub1_91.txt AC 311 ms 82824 KB
sub1_92.txt AC 315 ms 82800 KB
sub1_93.txt AC 311 ms 82784 KB
sub1_94.txt AC 55 ms 73800 KB