Submission #13353466


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, M;
int A[1010], B[1010], C[1010];
int D[1010], E[1010], F[1010];
//---------------------------------------------------------------------------------------------------
vector<int> xdic, ydic;
int W, H;
int tate[5010][5010];
int yoko[5010][5010];
void pre() {
    xdic.push_back(-inf);
    xdic.push_back(inf);
    xdic.push_back(0);
    ydic.push_back(-inf);
    ydic.push_back(inf);
    ydic.push_back(0);
    rep(i, 0, N) {
        xdic.push_back(A[i]);
        xdic.push_back(B[i]);
        ydic.push_back(C[i]);
    }
    rep(i, 0, M) {
        xdic.push_back(D[i]);
        ydic.push_back(E[i]);
        ydic.push_back(F[i]);
    }

    sort(all(xdic));
    xdic.erase(unique(all(xdic)), xdic.end());
    sort(all(ydic));
    ydic.erase(unique(all(ydic)), ydic.end());

    W = xdic.size();
    H = ydic.size();

    rep(i, 0, N) {
        int a = lower_bound(all(xdic), A[i]) - xdic.begin();
        int b = lower_bound(all(xdic), B[i]) - xdic.begin();
        int c = lower_bound(all(ydic), C[i]) - ydic.begin();
        tate[c][a]++;
        tate[c][b]--;
    }
    rep(y, 0, H) rep(x, 1, W) tate[y][x] += tate[y][x - 1];

    rep(i, 0, M) {
        int d = lower_bound(all(xdic), D[i]) - xdic.begin();
        int e = lower_bound(all(ydic), E[i]) - ydic.begin();
        int f = lower_bound(all(ydic), F[i]) - ydic.begin();
        yoko[e][d]++;
        yoko[f][d]--;
    }
    rep(x, 0, W) rep(y, 1, H) yoko[y][x] += yoko[y - 1][x];
}
//---------------------------------------------------------------------------------------------------
bool vis[5010][5010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
ll calc() {
    ll res = 0;
    queue<pair<int, int>> que;
    int stx = lower_bound(all(xdic), 0) - xdic.begin();
    int sty = lower_bound(all(ydic), 0) - ydic.begin();

    vis[sty][stx] = true;
    que.push({ stx, sty });

    while (!que.empty()) {
        int ix, iy;
        tie(ix, iy) = que.front(); que.pop();

        if (ix == 0 || ix == W - 1) return infl;
        if (iy == 0 || iy == H - 1) return infl;

        res += 1LL * (xdic[ix + 1] - xdic[ix]) * (ydic[iy + 1] - ydic[iy]);

        rep(d, 0, 4) {
            int ix2 = ix + dx[d];
            int iy2 = iy + dy[d];
            if (0 <= ix2 && ix2 < W && 0 <= iy2 && iy2 < H && !vis[iy2][ix2]) {
                if (ix == ix2) {
                    // yoko
                    if (tate[max(iy,iy2)][ix2]) continue;
                }
                else {
                    // tate
                    if (yoko[iy][max(ix, ix2)]) continue;
                }

                vis[iy2][ix2] = true;
                que.push({ ix2, iy2 });
            }
        }
    }

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i] >> B[i] >> C[i];
    rep(i, 0, M) cin >> D[i] >> E[i] >> F[i];

    pre();

    ll ans = calc();
    if (ans == infl) cout << "INF" << endl;
    else cout << ans << endl;
}





Submission Info

Submission Time
Task F - . (Single Dot)
User hamayanhamayan
Language C++ (GCC 9.2.1)
Score 600
Code Size 4420 Byte
Status
Exec Time 425 ms
Memory 112832 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 600 / 600 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 2 ms 3708 KB
sample_02.txt 2 ms 3620 KB
sub1_01.txt 49 ms 39332 KB
sub1_02.txt 27 ms 27876 KB
sub1_03.txt 21 ms 19628 KB
sub1_04.txt 15 ms 12484 KB
sub1_05.txt 100 ms 66928 KB
sub1_06.txt 35 ms 31604 KB
sub1_07.txt 35 ms 31516 KB
sub1_08.txt 22 ms 21448 KB
sub1_09.txt 25 ms 23152 KB
sub1_10.txt 124 ms 79748 KB
sub1_11.txt 5 ms 5992 KB
sub1_12.txt 3 ms 4300 KB
sub1_13.txt 2 ms 3744 KB
sub1_14.txt 2 ms 3852 KB
sub1_15.txt 3 ms 4184 KB
sub1_16.txt 2 ms 3616 KB
sub1_17.txt 23 ms 19900 KB
sub1_18.txt 33 ms 24120 KB
sub1_19.txt 34 ms 23792 KB
sub1_20.txt 27 ms 22636 KB
sub1_21.txt 21 ms 21312 KB
sub1_22.txt 33 ms 23540 KB
sub1_23.txt 22 ms 21400 KB
sub1_24.txt 32 ms 24244 KB
sub1_25.txt 25 ms 23228 KB
sub1_26.txt 35 ms 24412 KB
sub1_27.txt 24 ms 22588 KB
sub1_28.txt 26 ms 22760 KB
sub1_29.txt 23 ms 22096 KB
sub1_30.txt 23 ms 22864 KB
sub1_31.txt 21 ms 19664 KB
sub1_32.txt 21 ms 21888 KB
sub1_33.txt 23 ms 22636 KB
sub1_34.txt 27 ms 22976 KB
sub1_35.txt 36 ms 23480 KB
sub1_36.txt 24 ms 23608 KB
sub1_37.txt 34 ms 24208 KB
sub1_38.txt 12 ms 7360 KB
sub1_39.txt 8 ms 5816 KB
sub1_40.txt 34 ms 24332 KB
sub1_41.txt 6 ms 7492 KB
sub1_42.txt 2 ms 3900 KB
sub1_43.txt 2 ms 3796 KB
sub1_44.txt 2 ms 3824 KB
sub1_45.txt 2 ms 3912 KB
sub1_46.txt 2 ms 3740 KB
sub1_47.txt 13 ms 12208 KB
sub1_48.txt 20 ms 14000 KB
sub1_49.txt 15 ms 12968 KB
sub1_50.txt 16 ms 13860 KB
sub1_51.txt 13 ms 12712 KB
sub1_52.txt 15 ms 12492 KB
sub1_53.txt 15 ms 13492 KB
sub1_54.txt 23 ms 12884 KB
sub1_55.txt 287 ms 109660 KB
sub1_56.txt 279 ms 110804 KB
sub1_57.txt 170 ms 103128 KB
sub1_58.txt 269 ms 110372 KB
sub1_59.txt 264 ms 105660 KB
sub1_60.txt 162 ms 102468 KB
sub1_61.txt 90 ms 48148 KB
sub1_62.txt 246 ms 97320 KB
sub1_63.txt 6 ms 5872 KB
sub1_64.txt 104 ms 70464 KB
sub1_65.txt 15 ms 10216 KB
sub1_66.txt 25 ms 17548 KB
sub1_67.txt 7 ms 6496 KB
sub1_68.txt 17 ms 10312 KB
sub1_69.txt 15 ms 10444 KB
sub1_70.txt 12 ms 10528 KB
sub1_71.txt 2 ms 3688 KB
sub1_72.txt 2 ms 3736 KB
sub1_73.txt 1 ms 3636 KB
sub1_74.txt 62 ms 46632 KB
sub1_75.txt 17 ms 16680 KB
sub1_76.txt 153 ms 98052 KB
sub1_77.txt 3 ms 3756 KB
sub1_78.txt 3 ms 3796 KB
sub1_79.txt 3 ms 3808 KB
sub1_80.txt 3 ms 3736 KB
sub1_81.txt 3 ms 3724 KB
sub1_82.txt 3 ms 3868 KB
sub1_83.txt 2 ms 3812 KB
sub1_84.txt 11 ms 10876 KB
sub1_85.txt 13 ms 14556 KB
sub1_86.txt 2 ms 3852 KB
sub1_87.txt 2 ms 3840 KB
sub1_88.txt 2 ms 4044 KB
sub1_89.txt 419 ms 112820 KB
sub1_90.txt 414 ms 112704 KB
sub1_91.txt 415 ms 112808 KB
sub1_92.txt 425 ms 112824 KB
sub1_93.txt 415 ms 112832 KB
sub1_94.txt 2 ms 3756 KB