oj.uz

답안 #55193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55193 2018-07-06T09:42:24 Z Costin Andrei Oncescu(#1304) 절취선 (JOI14_ho_t5) C++11
20 / 100
 684 ms 39904 KB 
#include<bits/stdc++.h>

using namespace std;

int H, W, N, a1[100009], a2[100009], b1[100009], b2[100009];
long long edges, vertices;

int difX, difY;
vector < int > normX, normY;
map < int, int > mpX, mpY;
void read ()
{
    scanf ("%d %d %d", &W, &H, &N);
    for (int i=1; i<=N; i++)
    {
        scanf ("%d %d %d %d", &a1[i], &b1[i], &a2[i], &b2[i]);
        assert (a1[i] != a2[i] || b1[i] != b2[i]);///it's not a freaking dot
    }
    N ++, a1[N] = 0, b1[N] = 0, a2[N] = 0, b2[N] = H;
    N ++, a1[N] = 0, b1[N] = 0, a2[N] = W, b2[N] = 0;
    N ++, a1[N] = 0, b1[N] = H, a2[N] = W, b2[N] = H;
    N ++, a1[N] = W, b1[N] = 0, a2[N] = W, b2[N] = H;
    normX.resize (2 * N), normY.resize (2 * N);
    for (int i=1; i<=N; i++)
        normX[2 * i - 2] = a1[i], normX[2 * i - 1] = a2[i],
        normY[2 * i - 2] = b1[i], normY[2 * i - 1] = b2[i];
    sort (normX.begin (), normX.end ());
    normX.erase (unique (normX.begin (), normX.end ())), difX = normX.size ();
    sort (normY.begin (), normY.end ());
    normY.erase (unique (normY.begin (), normY.end ())), difY = normY.size ();
    for (int i=0; i<difX; i++)
        mpX[normX[i]] = i + 1;
    for (int i=0; i<difY; i++)
        mpY[normY[i]] = i + 1;
    for (int i=1; i<=N; i++)
        a1[i] = mpX[a1[i]], a2[i] = mpX[a2[i]],
        b1[i] = mpY[b1[i]], b2[i] = mpY[b2[i]];
}

namespace countVE {
    static int aibSZ, aib[300009], active[300009];
    static long long horEdges, verEdges;
    static vector < int > par[300009];
    static vector < pair < int, int > > perp[300009];

    void update (int pos, int val) {while (pos <= aibSZ) aib[pos] += val, pos += pos - (pos & (pos - 1));}
    int query (int pos) {int sum = 0; while (pos) sum += aib[pos], pos &= pos - 1; return sum;}
    int query (int l, int r) {l = max (l, 1), r = min (r, aibSZ); if (l > r) return 0; return query (r) - query (l - 1);}

    void sweepLR ()
    {
        for (int i=1; i<=N; i++)
            if (b1[i] == b2[i])
                par[a1[i]].push_back (b1[i]),
                par[a2[i]].push_back (-b1[i]);
            else
                perp[a1[i]].push_back ({b1[i], b2[i]});
        aibSZ = difY;
        for (int i=1; i<=difX; i++)
        {
            for (auto j : par[i])
                if (j > 0)
                    update (j, +1);
            for (auto sg : perp[i])
            {
                int l = sg.first, r = sg.second, curr = query (l + 1, r - 1);
                verEdges += 1 + curr;
                vertices += 2 + curr;
            }
            for (auto j : par[i])
                if (j < 0)
                    update (-j, -1);
        }
    }

    void sweepUD ()
    {
        for (int i=1; i<=N; i++)
            if (a1[i] == a2[i])
                par[b1[i]].push_back (a1[i]),
                par[b2[i]].push_back (-a1[i]);
            else
                perp[b1[i]].push_back ({a1[i], a2[i]});
        aibSZ = difX;
        for (int i=1; i<=difY; i++)
        {
            for (auto j : par[i])
                if (j > 0)
                    update (j, +1), active[j] = 1;
            for (auto sg : perp[i])
            {
                int l = sg.first, r = sg.second, curr = query (l + 1, r - 1);
                horEdges += 1 + curr;
                vertices += (!active[l]) + (!active[r]);
            }
            for (auto j : par[i])
                if (j < 0)
                    update (-j, -1), active[-j] = 0;
        }
    }

    void countVerticesEdges ()
    {
        sweepLR ();
        for (int i=1; i<=difX; i++)
            par[i].clear (), perp[i].clear ();
        sweepUD ();
        edges = horEdges + verEdges;
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read ();
countVE::countVerticesEdges ();
printf ("%lld\n", edges + 1 - vertices);

return 0;
}

Compilation message

2014_ho_t5.cpp: In function 'void read()':
2014_ho_t5.cpp:13:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &W, &H, &N);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:16:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d %d %d", &a1[i], &b1[i], &a2[i], &b2[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 14568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14568 KB Output is correct
2 Correct 18 ms 14828 KB Output is correct
3 Correct 49 ms 17232 KB Output is correct
4 Correct 15 ms 17232 KB Output is correct
5 Correct 18 ms 17232 KB Output is correct
6 Correct 684 ms 39904 KB Output is correct
7 Correct 29 ms 39904 KB Output is correct
8 Correct 358 ms 39904 KB Output is correct
9 Correct 359 ms 39904 KB Output is correct
10 Correct 299 ms 39904 KB Output is correct

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -