| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 55220 |
2018-07-06T11:58:52 Z |
Costin Andrei Oncescu(#1304) |
절취선 (JOI14_ho_t5) |
C++11 |
|
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]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
