| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 341886 |
2020-12-31T11:30:34 Z |
phathnv |
Plahte (COCI17_plahte) |
C++11 |
|
454 ms |
53104 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Trectangle{
int x, y, u, v, ind;
};
struct Tball{
int x, y, c;
};
struct Tdata{
int t, type, l, r, ind;
Tdata(int _t, int _type, int _l, int _r, int _ind){
t = _t;
type = _type;
l = _l;
r = _r;
ind = _ind;
}
};
struct TsegmentTree{
int n;
vector <vector<int>> d;
void insert(int id, int l, int r, int u, int v, int val){
if (v < l || r < u)
return;
if (u <= l && r <= v){
d[id].push_back(val);
return;
}
int mid = (l + r) >> 1;
insert(id << 1, l, mid, u, v, val);
insert(id << 1 | 1, mid + 1, r, u, v, val);
}
void remove(int id, int l, int r, int u, int v){
if (v < l || r < u)
return;
if (u <= l && r <= v){
d[id].pop_back();
return;
}
int mid = (l + r) >> 1;
remove(id << 1, l, mid, u, v);
remove(id << 1 | 1, mid + 1, r, u, v);
}
int find(int id, int l, int r, int u, int v){
if (v < l || r < u)
return -1;
if (u <= l && r <= v){
if (d[id].empty())
return -1;
return d[id].back();
}
int mid = (l + r) >> 1;
int res = find(id << 1, l, mid, u, v);
if (res == -1)
res = find(id << 1 | 1, mid + 1, r, u, v);
if (res == -1 && !d[id].empty())
res = d[id].back();
return res;
}
void init(int _n){
n = _n;
d.assign(n * 4 + 1, vector<int>());
}
void insert(int l, int r, int ind){
insert(1, 1, n, l, r, ind);
}
void remove(int l, int r){
remove(1, 1, n, l, r);
}
int find(int l, int r){
return find(1, 1, n, l, r);
}
};
const int mxN = 80001;
int n, m, answer[mxN];
Trectangle rec[mxN];
Tball b[mxN];
vector <int> adj[mxN];
set <int> color[mxN];
bool vst[mxN];
void ReadInput(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> rec[i].x >> rec[i].y >> rec[i].u >> rec[i].v;
rec[i].ind = i;
}
for(int i = 1; i <= m; i++)
cin >> b[i].x >> b[i].y >> b[i].c;
}
void Compress(){
vector <int> x, y;
for(int i = 1; i <= n; i++){
x.push_back(rec[i].x);
x.push_back(rec[i].u);
y.push_back(rec[i].y);
y.push_back(rec[i].v);
}
for(int i = 1; i <= m; i++){
x.push_back(b[i].x);
y.push_back(b[i].y);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
y.resize(unique(y.begin(), y.end()) - y.begin());
for(int i = 1; i <= n; i++){
rec[i].x = lower_bound(x.begin(), x.end(), rec[i].x) - x.begin() + 1;
rec[i].u = lower_bound(x.begin(), x.end(), rec[i].u) - x.begin() + 1;
rec[i].y = lower_bound(y.begin(), y.end(), rec[i].y) - y.begin() + 1;
rec[i].v = lower_bound(y.begin(), y.end(), rec[i].v) - y.begin() + 1;
}
for(int i = 1; i <= m; i++){
b[i].x = lower_bound(x.begin(), x.end(), b[i].x) - x.begin() + 1;
b[i].y = lower_bound(y.begin(), y.end(), b[i].y) - y.begin() + 1;
}
}
void Sweepline(){
vector <Tdata> event;
for(int i = 1; i <= n; i++){
event.push_back(Tdata(rec[i].y, 1, rec[i].x, rec[i].u, i));
event.push_back(Tdata(rec[i].v + 1, -1, rec[i].x, rec[i].u, i));
}
for(int i = 1; i <= m; i++)
event.push_back(Tdata(b[i].y, 2, b[i].x, b[i].x, b[i].c));
sort(event.begin(), event.end(), [](const Tdata &a, const Tdata &b){
if (a.t != b.t)
return a.t < b.t;
return a.type < b.type;
});
int maxX = 0;
for(int i = 1; i <= n; i++)
maxX = max(maxX, rec[i].u);
for(int i = 1; i <= m; i++)
maxX = max(maxX, b[i].x);
TsegmentTree ST;
ST.init(maxX);
for(Tdata e : event)
if (e.type == -1){
ST.remove(e.l, e.r);
} else if (e.type == 1){
int tmp = ST.find(e.l, e.r);
ST.insert(e.l, e.r, e.ind);
if (tmp != -1){
adj[tmp].push_back(e.ind);
//cerr << "edge " << tmp << ' ' << e.ind << endl;
}
} else {
int tmp = ST.find(e.l, e.r);
if (tmp != -1){
color[tmp].insert(e.ind);
//cerr << "col " << tmp << ' ' << e.ind << endl;
}
}
}
void Merge(set<int> &a, set<int> &b){
if (a.size() < b.size())
swap(a, b);
for(int x : b)
a.insert(x);
b.clear();
}
void Dfs(int u){
if (vst[u])
return;
vst[u] = 1;
for(int v : adj[u]){
Dfs(v);
Merge(color[u], color[v]);
}
answer[u] = color[u].size();
}
void Solve(){
for(int i = 1; i <= n; i++)
Dfs(i);
for(int i = 1; i <= n; i++)
cout << answer[i] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ReadInput();
Compress();
Sweepline();
Solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
17924 KB |
Output is correct |
| 2 |
Correct |
124 ms |
18948 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
21396 KB |
Output is correct |
| 2 |
Correct |
150 ms |
22336 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
32560 KB |
Output is correct |
| 2 |
Correct |
300 ms |
31600 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
441 ms |
53104 KB |
Output is correct |
| 2 |
Correct |
454 ms |
48616 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
454 ms |
52216 KB |
Output is correct |
| 2 |
Correct |
444 ms |
44904 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5996 KB |
Output is correct |
