| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55195 |
2018-07-06T09:47:14 Z |
강태규(#1525) |
None (JOI14_ho_t5) |
C++11 |
|
368 ms |
8100 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int w, h, n;
vector<int> compx, compy;
struct line {
int x1, x2, y;
bool operator<(const line &p) const {
return y < p.y;
}
void compress(const vector<int> &cx, const vector<int> &cy) {
x1 = lower_bound(cx.begin(), cx.end(), x1) - cx.begin() + 1;
x2 = lower_bound(cx.begin(), cx.end(), x2) - cx.begin() + 1;
y = lower_bound(cy.begin(), cy.end(), y) - cy.begin() + 1;
}
};
struct event {
int x, y, c;
bool operator<(const event &p) const {
return y < p.y;
}
};
int seg[1 << 19];
void update(int i, int s, int e, int x, int v) {
if (s == e) {
seg[i] += v;
return;
}
int m = (s + e) / 2;
if (x <= m) update(i << 1, s, m, x, v);
else update(i << 1 | 1, m + 1, e, x, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
int query(int i, int s, int e, int x, int y) {
if (e < x || y < s) return 0;
if (x <= s && e <= y) return seg[i];
int m = (s + e) / 2;
return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y);
}
pll getVertexEdges(int mx, const vector<line>& ls, const vector<line>& le) {
llong v = 0, e = 0;
vector<event> ev;
for (line i : le) {
ev.push_back({ i.y, i.x1, 1 });
ev.push_back({ i.y, i.x2 + 1, -1 });
}
sort(ev.begin(), ev.end());
int j = 0;
for (line i : ls) {
while (j < ev.size() && ev[j].y <= i.y)
update(1, 1, mx, ev[j].x, ev[j].c), ++j;
int ret1 = query(1, 1, mx, i.x1 + 1, i.x2 - 1);
int ret2 = query(1, 1, mx, i.x1, i.x2);
v += ret2;
e += max(ret2 - 1, 0);
}
while (j < ev.size())
update(1, 1, mx, ev[j].x, ev[j].c), ++j;
return pii(v, e);
}
int delX[100003];
int delY[100003];
int getComponentSize() {
return 1;
}
int main() {
scanf("%d%d%d", &w, &h, &n);
vector<line> lx, ly;
for (int i = 0; i < n; ++i) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if (b == d) lx.push_back({ a, c, b });
else ly.push_back({ b, d, a });
compx.push_back(a);
compx.push_back(c);
compy.push_back(b);
compy.push_back(d);
}
lx.push_back({ 0, w, 0 });
lx.push_back({ 0, w, h });
ly.push_back({ 0, h, 0 });
ly.push_back({ 0, h, w });
compx.push_back(0);
compx.push_back(w);
compy.push_back(0);
compy.push_back(h);
sort(compx.begin(), compx.end());
compx.erase(unique(compx.begin(), compx.end()), compx.end());
sort(compy.begin(), compy.end());
compy.erase(unique(compy.begin(), compy.end()), compy.end());
sort(lx.begin(), lx.end());
sort(ly.begin(), ly.end());
for (line &i : lx) i.compress(compx, compy);
for (line &i : ly) i.compress(compy, compx);
llong v, e1, e2;
tie(v, e1) = getVertexEdges(compx.size(), lx, ly);
tie(v, e2) = getVertexEdges(compy.size(), ly, lx);
llong e = e1 + e2;
llong c = getComponentSize();
printf("%lld\n", e - v + c);
return 0;
}
Compilation message
2014_ho_t5.cpp: In function 'pll getVertexEdges(int, const std::vector<line>&, const std::vector<line>&)':
2014_ho_t5.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < ev.size() && ev[j].y <= i.y)
~~^~~~~~~~~~~
2014_ho_t5.cpp:73:13: warning: unused variable 'ret1' [-Wunused-variable]
int ret1 = query(1, 1, mx, i.x1 + 1, i.x2 - 1);
^~~~
2014_ho_t5.cpp:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < ev.size())
~~^~~~~~~~~~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:90:10: 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:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &a, &b, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
520 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
576 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
520 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
576 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
620 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
624 KB |
Output is correct |
| 2 |
Correct |
5 ms |
624 KB |
Output is correct |
| 3 |
Correct |
35 ms |
1336 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1336 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1336 KB |
Output is correct |
| 6 |
Correct |
368 ms |
8100 KB |
Output is correct |
| 7 |
Correct |
21 ms |
8100 KB |
Output is correct |
| 8 |
Incorrect |
199 ms |
8100 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
520 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
576 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
