oj.uz

Submission #55220

# Submission time Handle Problem Language Result Execution time Memory
55220 2018-07-06T11:58:52 Z Costin Andrei Oncescu(#1304) None (JOI14_ho_t5) C++11
0 / 100
 3000 ms 169144 KB 
#include<bits/stdc++.h>

using namespace std;

int cntComps, 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 ()), normX.end ()), difX = normX.size ();
    sort (normY.begin (), normY.end ());
    normY.erase (unique (normY.begin (), normY.end ()), 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;
    }
}

bool ap[100009];
int firstEnd[100009], secondEnd[100009];
class dataStructure {
public:
    int aint[1200009];
    vector < int > lft[1200009], rgt[1200009];
    set < pair < int, int > > s[300009];
    int *aibL[1200009], *aibR[1200009];
    void add (int nod, int st, int dr, int pos, int l, int r)
    {
        aint[nod] ++;
        rgt[nod].push_back (r), lft[nod].push_back (l);
        if (st == dr) return ;
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (pos <= mij) add (f1, st, mij, pos, l, r);
        else add (f2, mij + 1, dr, pos, l, r);
    }

    void addToSet (int pos, int i)
    {
        s[pos].insert ({firstEnd[i], i});
    }

    void delFromSet (int pos, int i)
    {
        s[pos].erase ({firstEnd[i], i});
    }

    void build (int nod, int st, int dr)
    {
        sort (lft[nod].begin (), lft[nod].end ());
        sort (rgt[nod].begin (), rgt[nod].end ());
        int sz = lft[nod].size ();
        aibL[nod] = new int[sz + 1] (), aibR[nod] = new int[sz + 1] ();
        for (int i=1; i<=sz; i++)
            for (int j=0; (1 << j) <= i; j++)
                if (i & (1 << j))
                {
                    aibL[nod][i] = aibR[nod][i] = 1 << j;
                    break;
                }
        if (st == dr) return ;
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        build (f1, st, mij);
        build (f2, mij + 1, dr);
    }

    void updateL (int nod, int pos)
    {
        pos = lft[nod].size () + 1 - pos;
        while (pos <= lft[nod].size ())
            aibL[nod][pos] --, pos += pos - (pos & (pos - 1));
    }

    void updateR (int nod, int pos)
    {
        while (pos <= lft[nod].size ())
            aibR[nod][pos] --, pos += pos - (pos & (pos - 1));
    }

    int queryL (int nod, int pos)
    {
        pos = lft[nod].size () + 1 - pos;
        int ans = 0;
        while (pos)
            ans += aibL[nod][pos], pos &= pos - 1;
        return ans;
    }

    int queryR (int nod, int pos)
    {
        int ans = 0;
        while (pos)
            ans += aibR[nod][pos], pos &= pos - 1;
        return ans;
    }

    void del (int nod, int st, int dr, int pos, int l, int r)
    {
        int pL = lower_bound (lft[nod].begin (), lft[nod].end (), l) - lft[nod].begin () + 1;
        int pR = lower_bound (rgt[nod].begin (), rgt[nod].end (), r) - rgt[nod].begin () + 1;
        updateL (nod, pL);
        updateR (nod, pR);
        aint[nod] --;
        if (st == dr) return ;
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (pos <= mij) add (f1, st, mij, pos, l, r);
        else add (f2, mij + 1, dr, pos, l, r);
    }

    bool useless (int nod, int x)
    {
        int pL = lower_bound (lft[nod].begin (), lft[nod].end (), x + 1) - lft[nod].begin () + 1;
        int pR = lower_bound (rgt[nod].begin (), rgt[nod].end (), x) - rgt[nod].begin ();
        int cnt = queryL (nod, pL) + queryR (nod, pR);
        return (cnt == aint[nod]);
    }

    void findOnLine (int pos, int x, vector < int > &ans)
    {
        if (s[pos].empty ()) return ;
        auto it = s[pos].lower_bound ({x + 1, 0});
        if (it == s[pos].begin ()) return ;
        it --;
        if (secondEnd[it->second] < x) return ;
        ans.push_back (it->second), ap[it->second] = 1;
        del (1, 1, N, pos, firstEnd[it->second], secondEnd[it->second]);
        s[pos].erase (it);
    }

    void findInter (int nod, int st, int dr, int x, int y, int pos, vector < int > &ans)
    {
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (x <= st && dr <= y)
        {
            if (useless (nod, pos)) return ;
            if (st == dr)
            {
                findOnLine (st, pos, ans);
                return ;
            }
            findInter (f1, st, mij, x, y, pos, ans);
            findInter (f2, mij + 1, dr, x, y, pos, ans);
            return ;
        }
        if (x <= mij) findInter (f1, st, mij, x, y, pos, ans);
        if (mij < y) findInter (f2, mij + 1, dr, x, y, pos, ans);
    }
}v, h;

namespace countC {
    queue < int > cc;

    void bfs (int nod)
    {
        cc.push (nod), ap[nod] = 1;
        if (a1[nod] == a2[nod]) v.delFromSet (a1[nod], nod);
        else h.delFromSet (b1[nod], nod);
        while (!cc.empty ())
        {
            vector < int > curr;
            int nod = cc.front ();
            cc.pop ();
            if (a1[nod] == a2[nod])
                h.findInter (1, 1, difY, b1[nod], b2[nod], a1[nod], curr);
            else
                v.findInter (1, 1, difX, a1[nod], a2[nod], b1[nod], curr);
            for (auto it : curr)
                cc.push (it);
        }
    }

    void countComponents ()
    {
        for (int i=1; i<=N; i++)
            if (a1[i] == a2[i])
                firstEnd[i] = b1[i], secondEnd[i] = b2[i],
                v.add (1, 1, difX, a1[i], b1[i], b2[i]),
                v.addToSet (a1[i], i);
            else
                firstEnd[i] = a1[i], secondEnd[i] = a2[i],
                h.add (1, 1, difY, b1[i], a1[i], a2[i]),
                h.addToSet (b1[i], i);
        v.build (1, 1, difX);
        h.build (1, 1, difY);
        for (int i=1; i<=N; i++)
            if (ap[i] == 0)
                bfs (i), cntComps ++;
    }
}

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

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

return 0;
}

Compilation message

2014_ho_t5.cpp: In member function 'void dataStructure::updateL(int, int)':
2014_ho_t5.cpp:162:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pos <= lft[nod].size ())
                ~~~~^~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp: In member function 'void dataStructure::updateR(int, int)':
2014_ho_t5.cpp:168:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pos <= lft[nod].size ())
                ~~~~^~~~~~~~~~~~~~~~~~~
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

# Verdict Execution time Memory Grader output
1 Correct 123 ms 155512 KB Output is correct
2 Correct 139 ms 155512 KB Output is correct
3 Correct 138 ms 155548 KB Output is correct
4 Correct 137 ms 155624 KB Output is correct
5 Correct 141 ms 155764 KB Output is correct
6 Correct 146 ms 155764 KB Output is correct
7 Correct 163 ms 156060 KB Output is correct
8 Correct 147 ms 156476 KB Output is correct
9 Incorrect 149 ms 156476 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 155512 KB Output is correct
2 Correct 139 ms 155512 KB Output is correct
3 Correct 138 ms 155548 KB Output is correct
4 Correct 137 ms 155624 KB Output is correct
5 Correct 141 ms 155764 KB Output is correct
6 Correct 146 ms 155764 KB Output is correct
7 Correct 163 ms 156060 KB Output is correct
8 Correct 147 ms 156476 KB Output is correct
9 Incorrect 149 ms 156476 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 156476 KB Output is correct
2 Correct 160 ms 156476 KB Output is correct
3 Correct 161 ms 156476 KB Output is correct
4 Correct 173 ms 156988 KB Output is correct
5 Incorrect 507 ms 169008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 169008 KB Output is correct
2 Correct 181 ms 169008 KB Output is correct
3 Execution timed out 3039 ms 169144 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 155512 KB Output is correct
2 Correct 139 ms 155512 KB Output is correct
3 Correct 138 ms 155548 KB Output is correct
4 Correct 137 ms 155624 KB Output is correct
5 Correct 141 ms 155764 KB Output is correct
6 Correct 146 ms 155764 KB Output is correct
7 Correct 163 ms 156060 KB Output is correct
8 Correct 147 ms 156476 KB Output is correct
9 Incorrect 149 ms 156476 KB Output isn't correct
10 Halted 0 ms 0 KB -