#include <bits/stdc++.h>
#define X first
#define Y second
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
int n, m;
int a[80002];
int b[80002];
int c[80002];
int d[80002];
map< int, vector< pair<int, int> > > mp;
map< int, vector< pair<int, int> > > :: iterator it;
vector< pair<int, int> > tren;
vector<int> v[80002];
set< pair< pair<int, int>, int> > s;
set< pair< pair<int, int>, int> > :: iterator it2;
bitset<80002> p[80002];
int p1[80002];
int p2[80002];
int p3[80002];
vector<int> saz;
int bio[80002];
void dfs(int x) {
bio[x] = 1;
for (int i = 0; i < v[x].size(); i ++) {
int sus = v[x][i];
if (bio[sus] == 0) dfs(sus);
p[x] = p[x]|p[sus];
}
}
bool cmp(pair<int, int> q1, pair<int, int> q2) {
if (q1.Y == 0) return 1;
if (q2.Y == 0) return 0;
if (q1.Y < 0) return 1;
if (q2.Y < 0) return 0;
return 1;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i ++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
mp[a[i]].push_back({i, 0});
mp[c[i]].push_back({i, 1});
}
for (it = mp.begin(); it != mp.end(); it ++) {
tren = it -> second;
for (int i = 0; i < tren.size(); i ++) {
int w = tren[i].X;
int f = tren[i].Y;
if (f == 0) {
it2 = s.lower_bound({{b[w], 0}, 0});
if (it2 != s.end() && (it2 -> first).Y <= b[w]) {
v[(it2 -> second)].push_back(w);
}
s.insert({{d[w], b[w]}, w});
}
else {
s.erase({{d[w], b[w]}, w});
}
}
}
/*for (int i = 0; i < n; i ++) {
cout << i << ": ";
for (int j = 0; j < v[i].size(); j ++) cout << v[i][j] << " ";
cout << endl;
}*/
for (int i = 0; i < m; i ++) {
cin >> p1[i] >> p2[i] >> p3[i];
saz.push_back(p3[i]);
}
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
for (int i = 0; i < m; i ++) {
p3[i] = lower_bound(saz.begin(), saz.end(), p3[i]) - saz.begin();
p3[i] ++;
mp[ p1[i] ].push_back({i, -p3[i]});
}
for (it = mp.begin(); it != mp.end(); it ++) {
tren = it -> second;
sort(tren.begin(), tren.end(), cmp);
for (int i = 0; i < tren.size(); i ++) {
int w = tren[i].X;
int f = tren[i].Y;
if (f < 0) {
f *= -1;
f --;
it2 = s.lower_bound({{p2[w], 0}, 0});
if (it2 != s.end() && (it2 -> first).Y <= p2[w]) p[(it2 -> second)][f] = 1;
}
else if (f == 0) {
s.insert({{d[w], b[w]}, w});
}
else {
s.erase({{d[w], b[w]}, w});
}
}
}
for (int i = 0; i < n; i ++) {
if (bio[i] == 0) dfs(i);
cout << p[i].count() << endl;
}
return 0;
}
Compilation message
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[x].size(); i ++) {
~~^~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tren.size(); i ++) {
~~^~~~~~~~~~~~~
plahte.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tren.size(); i ++) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
149 ms |
17016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
240 ms |
17848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
259 ms |
28788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
403 ms |
42968 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
364 ms |
41840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
