| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79844 |
2018-10-16T18:59:32 Z |
pzdba |
Plahte (COCI17_plahte) |
C++14 |
|
514 ms |
62460 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<int> g[80005];
vector<int> h1, h2;
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(){
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<=3*n;i++){
for(int j=0;j<o1[i].size();j++){
int idx = o1[i][j];
int u1 = -1, u2 = -1;
its = sweep.upper_bound(pii(b[idx], 2e9));
if(its != sweep.begin()){
its--;
u1 = its->second;
if(!(b[u1] <= b[idx] && d[idx] <= d[u1])) u1 = -1;
}
its = sweep.lower_bound(pii(d[idx], 2e9));
if(its != sweep.end()){
u2 = its->second;
if(!(b[u2] <= b[idx] && d[idx] <= d[u2])) u2 = -1;
}
if(u1 != -1 && u2 != -1){
if(b[u1] <= b[u2]) g[u1].emplace_back(idx);
else g[u2].emplace_back(idx);
deg[idx]++;
}
else if(u1 != -1){
g[u1].emplace_back(idx);
deg[idx]++;
}
else if(u2 != -1){
g[u2].emplace_back(idx);
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];
int u1 = -1, u2 = -1;
its = sweep.upper_bound(pii(y[idx], 2e9));
if(its != sweep.begin()){
its--;
u1 = its->second;
if(!(b[u1] <= y[idx] && y[idx] <= d[u1])) u1 = -1;
}
its = sweep.lower_bound(pii(y[idx], 2e9));
if(its != sweep.end()){
u2 = its->second;
if(!(b[u2] <= y[idx] && y[idx] <= d[u2])) u2 = -1;
}
if(u1 != -1 && u2 != -1){
if(b[u1] <= b[u2]) sz[u2].insert(k[idx]);
else sz[u1].insert(k[idx]);
}
else if(u1 != -1){
sz[u1].insert(k[idx]);
}
else if(u2 != -1){
sz[u2].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:15: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:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o1[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o1[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o3[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<o2[i].size();j++){
~^~~~~~~~~~~~~
plahte.cpp:25: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:27: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:34: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 |
Incorrect |
144 ms |
30988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
173 ms |
35388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
45692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
59980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
514 ms |
62460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
