#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 w, f;
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 == q2.Y) return q1.X < q2.X;
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 ++) {
w = tren[i].X;
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]});
}
s.clear();
//cout << "DA" << endl;
/*for (it = mp.begin(); it != mp.end(); it ++) {
tren = (it -> second);
for (int i = 0; i < tren.size(); i ++) {
if (tren[i].X < 0) {
cout << "AAAAAAAAAAAAAAAAAAAA";
return 0;
}
}
}
cout << "Nije";
return 0;*/
/*cout << mp[22536502][1].X << " " << mp[22536502][1].Y << endl;
system("pause");*/
for (it = mp.begin(); it != mp.end(); it ++) {
//cout << (it -> first) << endl;
tren.clear();
tren = (it -> second);
//cout << "2: " << (it -> first) << endl;
sort(tren.begin(), tren.end(), cmp);
//cout << (it -> first) << " ," << tren.size() << endl;
for (int i = 0; i < tren.size(); i ++) {
//cout << i << endl;
w = tren[i].X;
f = tren[i].Y;
//cout << w << " " << f << endl;
if (w < 0) {
continue;
//cout << w << " RIP";
//system("pause");
}
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) {
//cout << "Nula" << endl;
s.insert({{d[w], b[w]}, w});
//cout << "Nula2" << endl;
}
else {
//cout << ">0" << endl;
//cout << "w je " << w << endl;
it2 = s.find({{d[w], b[w]}, w});
//cout << "wut" << endl;
//if (it2 == s.end()) cout << "RIP" << endl;
s.erase({{d[w], b[w]}, w});
//cout << ">0 2" << endl;
}
}
}
//cout << "DA2" << endl;
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:31: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:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tren.size(); i ++) {
~~^~~~~~~~~~~~~
plahte.cpp:124: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 |
114 ms |
17780 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 |
149 ms |
18396 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 |
235 ms |
29512 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 |
392 ms |
43532 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 |
410 ms |
42604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
