| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79848 |
2018-10-16T19:43:00 Z |
pzdba |
Plahte (COCI17_plahte) |
C++14 |
|
471 ms |
50980 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<int> g[80005];
vector<int> h1, h2;
int par[80005];
int deg[80005];
pii p[80005];
int a[80005], b[80005], c[80005], d[80005];
int x[80005], y[80005], k[80005];
vector<int> o1[240005], o2[240005], o3[240005];
set<int> sz[80005];
set<int>::iterator its;
int ans[80005];
void dfs(int u){
for(int i=0;i<g[u].size();i++){
int v = g[u][i];
dfs(v);
if(sz[v].size() > sz[u].size()) swap(sz[u], sz[v]);
for(its = sz[v].begin(); its != sz[v].end();its++) sz[u].insert(*its);
}
ans[u] = sz[u].size();
}
int main(){
memset(par, -1, sizeof(par));
int n, m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
h1.emplace_back(a[i]);
h1.emplace_back(c[i]);
h2.emplace_back(b[i]);
h2.emplace_back(d[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d", &x[i], &y[i], &k[i]);
h1.emplace_back(x[i]);
h2.emplace_back(y[i]);
}
sort(h1.begin(), h1.end());
sort(h2.begin(), h2.end());
h1.erase(unique(h1.begin(), h1.end()), h1.end());
h2.erase(unique(h2.begin(), h2.end()), h2.end());
for(int i=1;i<=n;i++){
a[i] = lower_bound(h1.begin(), h1.end(), a[i]) - h1.begin() + 1;
c[i] = lower_bound(h1.begin(), h1.end(), c[i]) - h1.begin() + 1;
b[i] = lower_bound(h2.begin(), h2.end(), b[i]) - h2.begin() + 1;
d[i] = lower_bound(h2.begin(), h2.end(), d[i]) - h2.begin() + 1;
}
for(int i=1;i<=m;i++){
x[i] = lower_bound(h1.begin(), h1.end(), x[i]) - h1.begin() + 1;
y[i] = lower_bound(h2.begin(), h2.end(), y[i]) - h2.begin() + 1;
}
set<pii> sweep;
set<pii>::iterator its;
for(int i=1;i<=n;i++){
o1[a[i]].emplace_back(i);
o2[c[i]].emplace_back(i);
}
for(int i=1;i<=m;i++){
o3[x[i]].emplace_back(i);
}
for(int i=1;i<=240000;i++){
for(int j=0;j<o1[i].size();j++){
int idx = o1[i][j];
its = sweep.upper_bound(pii(b[idx], 2e9));
if(its != sweep.begin()) its--;
if(its != sweep.end()){
int u = its->second;
if(!(b[u] <= b[idx] && d[idx] <= d[u])) u = par[u];
if(u == -1 || !(b[u] <= b[idx] && b[idx] <= d[u])) u = -1;
if(u != -1){
g[u].emplace_back(idx);
par[idx] = u;
deg[idx]++;
}
}
}
for(int j=0;j<o1[i].size();j++){
int idx = o1[i][j];
sweep.insert(pii(b[idx], idx));
sweep.insert(pii(d[idx], idx));
}
for(int j=0;j<o3[i].size();j++){
int idx = o3[i][j];
its = sweep.upper_bound(pii(y[idx], 2e9));
if(its != sweep.begin()) its--;
if(its != sweep.end()){
int u = its->second;
if(!(b[u] <= y[idx] && y[idx] <= d[u])) u = par[u];
if(u == -1 || !(b[u] <= y[idx] && y[idx] <= d[u])) u = -1;
if(u != -1){
sz[u].insert(k[idx]);
}
}
}
for(int j=0;j<o2[i].size();j++){
int idx = o2[i][j];
sweep.erase(sweep.find(pii(b[idx], idx)));
sweep.erase(sweep.find(pii(d[idx], idx)));
}
}
for(int i=1;i<=n;i++){
if(deg[i] == 0) dfs(i);
}
for(int i=1;i<=n;i++) printf("%d\n", ans[i]);
}
Compilation message
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o1[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o1[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o3[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:98:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o2[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x[i], &y[i], &k[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
30056 KB |
Output is correct |
| 2 |
Correct |
140 ms |
32296 KB |
Output is correct |
| 3 |
Correct |
23 ms |
32296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
34152 KB |
Output is correct |
| 2 |
Correct |
187 ms |
34152 KB |
Output is correct |
| 3 |
Correct |
28 ms |
34152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
41700 KB |
Output is correct |
| 2 |
Correct |
265 ms |
41700 KB |
Output is correct |
| 3 |
Correct |
23 ms |
41700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
468 ms |
50980 KB |
Output is correct |
| 2 |
Correct |
460 ms |
50980 KB |
Output is correct |
| 3 |
Correct |
23 ms |
50980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
471 ms |
50980 KB |
Output is correct |
| 2 |
Correct |
458 ms |
50980 KB |
Output is correct |
| 3 |
Correct |
23 ms |
50980 KB |
Output is correct |
