#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int OFF = (1 << 18);
int n, m;
int x[80002];
int y[80002];
int x2[80002];
int y2[80002];
int p1[80002];
int p2[80002];
int b[80002];
vector<int> saz;
vector< pair<int, int> > v[480002];
set<int> s[80002];
set<int> :: iterator it;
int f, w;
int sad = 1;
int koji[80002];
int mset[80002];
vector<int> sus[80002];
stack<int> tour[2*OFF+5];
int maxibr = 0;
void trazi(int l1, int r1, int lo, int hi, int c) {
//cout << l1 << " " << r1 << " " << lo << " " << hi << " " << c << endl;
if (hi <= l1 || r1 <= lo) return;
if (l1 <= lo && hi <= r1) {
int gdje = c;
while (gdje > 0) {
maxibr = max(maxibr, tour[gdje].top());
gdje /= 2;
}
//cout << "da: " << l1 << " " << r1 << " " << lo << " " << hi << endl;
tour[c].push(koji[w]);
return;
}
trazi(l1, r1, lo, (lo+hi)/2, c*2);
trazi(l1, r1, (lo+hi)/2, hi, c*2+1);
}
void makni(int l1, int r1, int lo, int hi, int c) {
if (hi <= l1 || r1 <= lo) return;
if (l1 <= lo && hi <= r1) {
tour[c].pop();
return;
}
makni(l1, r1, lo, (lo+hi)/2, c*2);
makni(l1, r1, (lo+hi)/2, hi, c*2+1);
}
void stavi(int l1, int r1, int lo, int hi, int c) {
if (hi <= l1 || r1 <= lo) return;
if (l1 <= lo && hi <= r1) {
int gdje = c;
//cout << l1 << " " << r1 << " " << lo << " " << hi << endl;
while (gdje > 0) {
s[tour[gdje].top()].insert(b[w]);
//cout << tour[gdje].top() << endl;
gdje /= 2;
}
return;
}
stavi(l1, r1, lo, (lo+hi)/2, c*2);
stavi(l1, r1, (lo+hi)/2, hi, c*2+1);
}
int rj[80002];
void rek(int tren) {
if (tren == 0) {
for (int i = 0; i < sus[0].size(); i ++) {
rek(sus[0][i]);
}
return;
}
if (sus[tren].size() == 0) {
rj[tren] = s[ mset[tren] ].size();
return;
}
for (int i = 0; i < sus[tren].size(); i ++) {
rek(sus[tren][i]);
}
int najv = 0, ind = 0;
for (int i = 0; i < sus[tren].size(); i ++) {
int slj = sus[tren][i];
if (s[ mset[slj] ].size() > najv) {
najv = s[ mset[slj] ].size();
ind = i;
}
}
for (it = s[ mset[tren] ].begin(); it != s[ mset[tren] ].end(); it ++) {
s[ mset[ sus[tren][ind] ] ].insert(*it);
}
mset[tren] = mset[ sus[tren][ind] ];
for (int i = 0; i < sus[tren].size(); i ++) {
if (i != ind) {
int slj = sus[tren][i];
for (it = s[ mset[slj] ].begin(); it != s[ mset[slj] ].end(); it ++) {
s[ mset[tren] ].insert(*it);
}
}
}
rj[tren] = s[ mset[tren] ].size();
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i ++) {
cin >> x[i] >> y[i] >> x2[i] >> y2[i];
saz.push_back(x[i]);
//saz.push_back(y[i]);
saz.push_back(x2[i]);
//saz.push_back(y2[i]);
}
for (int i = 0; i < m; i ++) {
cin >> p1[i] >> p2[i] >> b[i];
saz.push_back(p1[i]);
//saz.push_back(p2[i]);
}
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
for (int i = 0; i < n; i ++) {
x[i] = lower_bound(saz.begin(), saz.end(), x[i]) - saz.begin();
//y[i] = lower_bound(saz.begin(), saz.end(), y[i]) - saz.begin();
x2[i] = lower_bound(saz.begin(), saz.end(), x2[i]) - saz.begin();
//y2[i] = lower_bound(saz.begin(), saz.end(), y2[i]) - saz.begin();
//cout << "(" << x[i] << "," << y[i] << ") -> (" << x2[i] << "," << y2[i] << ")" << endl;
v[x[i]].push_back({-1, i});
v[x2[i]].push_back({1, i});
}
for (int i = 0; i < m; i ++) {
p1[i] = lower_bound(saz.begin(), saz.end(), p1[i]) - saz.begin();
//p2[i] = lower_bound(saz.begin(), saz.end(), p2[i]) - saz.begin();
//cout << "(" << p1[i] << "," << p2[i] << ")" << endl;
v[p1[i]].push_back({0, i});
}
saz.clear();
for (int i = 0; i < n; i ++) {
//saz.push_back(x[i]);
saz.push_back(y[i]);
//saz.push_back(x2[i]);
saz.push_back(y2[i]);
}
for (int i = 0; i < m; i ++) {
//saz.push_back(p1[i]);
saz.push_back(p2[i]);
}
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
for (int i = 0; i < n; i ++) {
//x[i] = lower_bound(saz.begin(), saz.end(), x[i]) - saz.begin();
y[i] = lower_bound(saz.begin(), saz.end(), y[i]) - saz.begin();
//x2[i] = lower_bound(saz.begin(), saz.end(), x2[i]) - saz.begin();
y2[i] = lower_bound(saz.begin(), saz.end(), y2[i]) - saz.begin();
}
for (int i = 0; i < m; i ++) {
//p1[i] = lower_bound(saz.begin(), saz.end(), p1[i]) - saz.begin();
p2[i] = lower_bound(saz.begin(), saz.end(), p2[i]) - saz.begin();
}
saz.clear();
for (int i = 0; i < m; i ++) {
saz.push_back(b[i]);
}
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
for (int i = 0; i < m; i ++) {
b[i] = lower_bound(saz.begin(), saz.end(), b[i]) - saz.begin();
}
for (int i = 0; i <= 2*OFF; i ++) tour[i].push(0);
for (int i = 0; i <= 480000; i ++) {
sort(v[i].begin(), v[i].end());
for (int j = 0; j < v[i].size(); j ++) {
f = v[i][j].X;
w = v[i][j].Y;
if (f == -1) koji[w] = sad, sad ++;
if (f == -1) {
maxibr = 0;
trazi(y[w], y2[w]+1, 0, OFF, 1);
sus[maxibr].push_back(koji[w]);
}
else if (f == 0) {
//cout << "DA!" << endl;
stavi(p2[w], p2[w]+1, 0, OFF, 1);
}
else {
makni(y[w], y2[w]+1, 0, OFF, 1);
}
//cout << f << ": " << w << endl;
/*int pr = 2;
for (int k = 1; k < OFF*2; k ++) {
if (k == pr) {
cout << endl;
pr *= 2;
}
cout << tour[k].top() << " ";
}
cout << endl;*/
}
}
for (int i = 1; i < sad; i ++) mset[i] = i;
rek(0);
/*for (int i = 0; i <= n; i ++) {
cout << i << ": ";
for (int j = 0; j < sus[i].size(); j ++) cout << sus[i][j] << " ";
cout << endl;
}*/
for (int i = 1; i <= n; i ++) {
//cout << "KOJI: " << koji[i] << endl;
//cout << p[koji[i-1]].count() << endl;
cout << rj[ koji[i-1] ] << endl;
}
return 0;
}
Compilation message
plahte.cpp: In function 'void rek(int)':
plahte.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sus[0].size(); i ++) {
~~^~~~~~~~~~~~~~~
plahte.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sus[tren].size(); i ++) {
~~^~~~~~~~~~~~~~~~~~
plahte.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sus[tren].size(); i ++) {
~~^~~~~~~~~~~~~~~~~~
plahte.cpp:102:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (s[ mset[slj] ].size() > najv) {
~~~~~~~~~~~~~~~~~~~~~~^~~~~~
plahte.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sus[tren].size(); i ++) {
~~^~~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:207:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); j ++) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
708 ms |
380428 KB |
Output is correct |
| 2 |
Correct |
709 ms |
380496 KB |
Output is correct |
| 3 |
Correct |
422 ms |
370328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
777 ms |
382832 KB |
Output is correct |
| 2 |
Correct |
802 ms |
381532 KB |
Output is correct |
| 3 |
Correct |
468 ms |
370296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1113 ms |
392180 KB |
Output is correct |
| 2 |
Correct |
1036 ms |
390144 KB |
Output is correct |
| 3 |
Correct |
411 ms |
370240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1678 ms |
403596 KB |
Output is correct |
| 2 |
Correct |
1520 ms |
404716 KB |
Output is correct |
| 3 |
Correct |
408 ms |
370392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1798 ms |
403612 KB |
Output is correct |
| 2 |
Correct |
1458 ms |
400236 KB |
Output is correct |
| 3 |
Correct |
403 ms |
370300 KB |
Output is correct |
