| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 868618 |
2023-11-01T02:25:25 Z |
hgmhc |
None (JOI14_ho_t5) |
C++17 |
|
283 ms |
35492 KB |
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
const int M = 2e5+10;
int w, h, n;
vector<pair<int,int>> ver[M], hor[M];
namespace sub4 {
template <const int N>
struct fenwick {
int t[N+1]{};
void add(int k, int x) {
for (++k; k <= N; k += k&-k) t[k] += x;
}
int sum(int a, int b) {
int r = 0;
for (; a >= 1; a -= a&-a) r -= t[a];
for (++b; b >= 1; b -= b&-b) r += t[b];
return r;
}
};
fenwick<M> ds;
int64_t sweep_v() {
// 꼭짓점 말고 교차점만 카운트
vector<int> in[M], out[M];
rep(i,0,M-1) {
for (auto [x1,x2] : hor[i]) {
if (x1 > x2) swap(x1,x2);
in[x1].push_back(i);
out[x2].push_back(i);
}
}
int64_t res = 0;
rep(i,0,M-1) {
for (auto y : in[i]) ds.add(y,+1);
for (auto [y1,y2] : ver[i]) {
if (y1 > y2) swap(y1,y2);
res += ds.sum(y1,y2);
}
for (auto y : out[i]) ds.add(y,-1);
}
return res;
}
int64_t sweep_e() {
// 선분마다 꼭짓점은 무시하고 교차점-1로 카운트
vector<int> in[M], out[M];
rep(i,0,M-1) {
for (auto [x1,x2] : hor[i]) {
if (x1 > x2) swap(x1,x2);
in[x1].push_back(i);
out[x2].push_back(i);
}
}
int64_t res = 0;
rep(i,0,M-1) {
for (auto y : in[i]) ds.add(y,+1);
for (auto [y1,y2] : ver[i]) {
if (y1 > y2) swap(y1,y2);
res += max(0,ds.sum(y1,y2)-1);
}
for (auto y : out[i]) ds.add(y,-1);
}
return res;
}
int64_t get_v() {
int64_t res = sweep_v();
swap(ver,hor);
res += sweep_v();
return res;
}
int64_t get_e() {
int64_t res = sweep_e();
swap(ver,hor);
res += sweep_e();
return res;
}
}
int p[2*M], cnt=0;
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
int merge(int a, int b) {
int x=a, y=b;
if (a == 0) return b;
if (b == 0) return a;
a = find(a), b = find(b);
if (a == b) return a;
// cerr << x << ' ' << y << endl;
cnt++;
p[b] = a;
return a;
}
// 5 4 9
// 0 1 2 1
// 3 1 4 1
// 1 0 1 3
// 0 2 4 2
// 3 3 3 1
// 4 1 4 0
// 3 3 4 3
// 4 2 4 3
// 2 1 2 4
// answer: 7
// [a,b]에 뭐라도 남아있다면,
// 양 자식에 레이지 합치기
template <const int N=1<<18>
struct segtree {
int t[2*N]{}, sum[2*N]{};
segtree(){ iota(p,p+2*M,0); }
void insert(int i, int c, int k, int s, int e) {
if (s == i and i == e) { t[k] = c; return; }
if (sum[2*k]) t[2*k] = merge(t[2*k],t[k]);
if (sum[2*k+1]) t[2*k+1] = merge(t[2*k+1],t[k]);
t[k]=0;
int m = (s+e)/2;
if (i <= m) insert(i,c,2*k,s,m);
else insert(i,c,2*k+1,m+1,e);
}
void insert(int i, int c) {
insert(i,c,1,0,N-1);
assert(!sum[i+=N]);
for (; i >= 1; i /= 2) sum[i]++;
}
void erase(int i) {
int c = t[i+=N];
assert(sum[i]), t[i] = 0;
for (; i >= 1; i /= 2) sum[i]--, c = merge(c,t[i]);
}
void join(int a, int b, int c) {
for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
if (a&1) {
if (sum[a]) merge(c,t[a]);
t[a]=c;
}
if (~b&1) {
if (sum[b]) merge(c,t[b]);
t[b]=c;
}
}
}
};
segtree<> ds;
int64_t get_c() {
vector<int> in[M], out[M];
rep(i,0,M-1) {
for (auto [x1,x2] : hor[i]) {
if (x1 > x2) swap(x1,x2);
in[x1].push_back(i);
out[x2].push_back(i);
}
}
int clr = 0;
rep(i,0,M-1) {
for (auto y : in[i]) ds.insert(y,++clr);
for (auto [y1,y2] : ver[i]) {
if (y1 > y2) swap(y1,y2);
ds.join(y1,y2,++clr);
}
for (auto y : out[i]) ds.erase(y);
// cerr << clr << ' ' << cnt << endl;
}
return clr-cnt;
}
void solve() {
int64_t v = sub4::get_v() / 2LL;
int64_t e = sub4::get_e();
int64_t f = get_c()-v+e;
cout << f;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> w >> h >> n;
vector<array<int,4>> segments(n);
vector<int> xs, ys;
xs.push_back(0), xs.push_back(w);
ys.push_back(0), ys.push_back(h);
for (auto &[a,b,c,d] : segments) {
cin >> a >> b >> c >> d;
xs.push_back(a), xs.push_back(c);
ys.push_back(b), ys.push_back(d);
}
segments.push_back({w,0,0,0});
segments.push_back({w,h,0,h});
segments.push_back({w,0,w,h});
segments.push_back({0,h,0,0});
sort(begin(xs),end(xs)), xs.erase(unique(begin(xs),end(xs)),end(xs));
sort(begin(ys),end(ys)), ys.erase(unique(begin(ys),end(ys)),end(ys));
for (auto &[a,b,c,d] : segments) {
a = lower_bound(begin(xs),end(xs),a)-begin(xs);
b = lower_bound(begin(ys),end(ys),b)-begin(ys);
c = lower_bound(begin(xs),end(xs),c)-begin(xs);
d = lower_bound(begin(ys),end(ys),d)-begin(ys);
// cerr << a << ' ' << b << ' ' << c << ' ' << d << endl;
if (a == c) {
ver[a].push_back({b,d});
} else {
hor[b].push_back({a,c});
}
}
solve();
}
Compilation message
2014_ho_t5.cpp: In function 'int merge(int, int)':
2014_ho_t5.cpp:93:6: warning: unused variable 'x' [-Wunused-variable]
93 | int x=a, y=b;
| ^
2014_ho_t5.cpp:93:11: warning: unused variable 'y' [-Wunused-variable]
93 | int x=a, y=b;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
25432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
25432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
25688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
25688 KB |
Output is correct |
| 2 |
Correct |
20 ms |
25688 KB |
Output is correct |
| 3 |
Correct |
37 ms |
26556 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25432 KB |
Output is correct |
| 5 |
Correct |
22 ms |
25692 KB |
Output is correct |
| 6 |
Correct |
283 ms |
35492 KB |
Output is correct |
| 7 |
Correct |
29 ms |
26300 KB |
Output is correct |
| 8 |
Correct |
115 ms |
34208 KB |
Output is correct |
| 9 |
Correct |
128 ms |
33440 KB |
Output is correct |
| 10 |
Correct |
127 ms |
32532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
25432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
