| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 332327 |
2020-12-02T03:49:07 Z |
arnold518 |
None (JOI14_ho_t5) |
C++14 |
|
160 ms |
262148 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXV = 6e6;
struct Line
{
int x1, y1, x2, y2, p;
};
int W, H, N, M, SX, SY;
Line A[MAXN+10], B[MAXN+10];
vector<int> xcomp, ycomp;
ll V, E, C=1;
struct BIT
{
int tree[MAXN+10];
void update(int i, int x) { for(; i<=SY; i+=(i&-i)) tree[i]+=x; }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
int query(int l, int r) { return query(r)-query(l-1); }
}bit;
struct Node
{
int lc, rc;
Node() : lc(-1), rc(-1) {}
};
Node nodes[MAXV+10];
int ncnt;
vector<int> adj[MAXV];
vector<int> radj[MAXV];
int newNode()
{
if(ncnt+1==MAXV) while(1);
return ++ncnt;
}
void addEdge(int u, int v)
{
//printf("%d %d\n", u, v);
adj[u].push_back(v);
radj[v].push_back(u);
}
void makeTree(int node, int tl, int tr)
{
if(tl==tr) return;
int mid=tl+tr>>1;
nodes[node].lc=newNode();
nodes[node].rc=newNode();
addEdge(nodes[node].lc, node);
addEdge(nodes[node].rc, node);
makeTree(nodes[node].lc, tl, mid);
makeTree(nodes[node].rc, mid+1, tr);
}
int update(int node, int tl, int tr, int p, int k)
{
if(p<tl || tr<p) return node;
int ret=newNode();
if(tl==tr)
{
if(k>0) addEdge(k, ret);
return ret;
}
int mid=tl+tr>>1;
nodes[ret].lc=update(nodes[node].lc, tl, mid, p, k);
nodes[ret].rc=update(nodes[node].rc, mid+1, tr, p, k);
addEdge(nodes[ret].lc, ret);
addEdge(nodes[ret].rc, ret);
return ret;
}
void query(int node, int tl, int tr, int l, int r, int k)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
addEdge(node, k);
return;
}
int mid=tl+tr>>1;
query(nodes[node].lc, tl, mid, l, r, k);
query(nodes[node].rc, mid+1, tr, l, r, k);
}
bool vis[MAXV+10];
vector<int> S;
void dfs(int now)
{
vis[now]=true;
for(int nxt : adj[now])
{
if(vis[nxt]) continue;
dfs(nxt);
}
S.push_back(now);
}
int scc[MAXV+10], scnt;
void dfs2(int now)
{
scc[now]=scnt;
for(int nxt : radj[now])
{
if(scc[nxt]) continue;
dfs2(nxt);
}
}
int main()
{
int t;
scanf("%d%d%d", &W, &H, &t);
for(int i=1; i<=t; i++)
{
Line p;
scanf("%d%d%d%d", &p.x1, &p.y1, &p.x2, &p.y2);
xcomp.push_back(p.x1);
xcomp.push_back(p.x2);
ycomp.push_back(p.y1);
ycomp.push_back(p.y2);
if(p.x1==p.x2) B[++M]=p;
else A[++N]=p;
}
xcomp.push_back(0);
ycomp.push_back(0);
xcomp.push_back(W);
ycomp.push_back(H);
A[++N]={0, 0, W, 0};
A[++N]={0, H, W, H};
B[++M]={0, 0, 0, H};
B[++M]={W, 0, W, H};
sort(xcomp.begin(), xcomp.end());
xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
sort(ycomp.begin(), ycomp.end());
ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
SX=xcomp.size(); SY=ycomp.size();
for(int i=1; i<=N; i++)
{
A[i].x1=lower_bound(xcomp.begin(), xcomp.end(), A[i].x1)-xcomp.begin()+1;
A[i].x2=lower_bound(xcomp.begin(), xcomp.end(), A[i].x2)-xcomp.begin()+1;
A[i].y1=lower_bound(ycomp.begin(), ycomp.end(), A[i].y1)-ycomp.begin()+1;
A[i].y2=lower_bound(ycomp.begin(), ycomp.end(), A[i].y2)-ycomp.begin()+1;
A[i].p=newNode();
}
for(int i=1; i<=M; i++)
{
B[i].x1=lower_bound(xcomp.begin(), xcomp.end(), B[i].x1)-xcomp.begin()+1;
B[i].x2=lower_bound(xcomp.begin(), xcomp.end(), B[i].x2)-xcomp.begin()+1;
B[i].y1=lower_bound(ycomp.begin(), ycomp.end(), B[i].y1)-ycomp.begin()+1;
B[i].y2=lower_bound(ycomp.begin(), ycomp.end(), B[i].y2)-ycomp.begin()+1;
B[i].p=newNode();
}
for(int i=1; i<=N; i++)
{
E+=A[i].x2-A[i].x1;
V+=A[i].x2-A[i].x1+1;
}
for(int i=1; i<=M; i++)
{
E+=B[i].y2-B[i].y1;
V+=B[i].y2-B[i].y1+1;
}
sort(B+1, B+M+1, [&](const Line &p, const Line &q)
{
return p.x1<q.x1;
});
vector<pair<pll, int>> VV;
for(int i=1; i<=N; i++)
{
VV.push_back({{A[i].x1, A[i].y1}, 1});
VV.push_back({{A[i].x2+1, A[i].y1}, -1});
}
sort(VV.begin(), VV.end());
for(int i=1, j=0; i<=M; i++)
{
for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
{
bit.update(VV[j].first.second, VV[j].second);
}
V-=bit.query(B[i].y1, B[i].y2);
}
int root;
VV.clear();
for(int i=1; i<=N; i++)
{
VV.push_back({{A[i].x1, A[i].y1}, A[i].p});
VV.push_back({{A[i].x2+1, A[i].y1}, 0});
}
sort(VV.begin(), VV.end());
root=newNode();
makeTree(root, 1, SY);
for(int i=1, j=0; i<=M; i++)
{
for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
{
root=update(root, 1, SY, VV[j].first.second, VV[j].second);
//printf("!!%d\n", VV[j].second);
}
query(root, 1, SY, B[i].y1, B[i].y2, B[i].p);
//printf("??%d\n", B[i].p);
}
VV.clear();
for(int i=1; i<=M; i++)
{
VV.push_back({{B[i].y1, B[i].x1}, B[i].p});
VV.push_back({{B[i].y2+1, B[i].x1}, 0});
}
sort(VV.begin(), VV.end());
sort(A+1, A+N+1, [&](const Line &p, const Line &q)
{
return p.y1<q.y1;
});
root=newNode();
makeTree(root, 1, SX);
for(int i=1, j=0; i<=N; i++)
{
for(; j<VV.size() && VV[j].first.first<=A[i].y1; j++)
{
root=update(root, 1, SX, VV[j].first.second, VV[j].second);
}
query(root, 1, SX, A[i].x1, A[i].x2, A[i].p);
}
for(int i=1; i<=ncnt; i++)
{
if(vis[i]) continue;
dfs(i);
}
reverse(S.begin(), S.end());
for(auto it : S)
{
if(scc[it]) continue;
++scnt;
dfs2(it);
}
set<int> SS;
for(int i=1; i<=N+M; i++) SS.insert(scc[i]);
C=SS.size();
ll ans=C-V+E;
printf("%lld\n", ans);
}
Compilation message
2014_ho_t5.cpp: In function 'void makeTree(int, int, int)':
2014_ho_t5.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int mid=tl+tr>>1;
| ~~^~~
2014_ho_t5.cpp: In function 'int update(int, int, int, int, int)':
2014_ho_t5.cpp:76:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid=tl+tr>>1;
| ~~^~~
2014_ho_t5.cpp: In function 'void query(int, int, int, int, int, int)':
2014_ho_t5.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid=tl+tr>>1;
| ~~^~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:197:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
| ~^~~~~~~~~~
2014_ho_t5.cpp:218:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | for(; j<VV.size() && VV[j].first.first<=B[i].x1; j++)
| ~^~~~~~~~~~
2014_ho_t5.cpp:243:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
243 | for(; j<VV.size() && VV[j].first.first<=A[i].y1; j++)
| ~^~~~~~~~~~
2014_ho_t5.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
124 | scanf("%d%d%d", &W, &H, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%d%d%d%d", &p.x1, &p.y1, &p.x2, &p.y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
160 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
160 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
144 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
160 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
