#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int OFF = (1 << 10);
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];
bitset<1000> p[80000];
int f, w;
int sad = 1;
int koji[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) {
p[tour[gdje].top()][b[w]] = 1;
//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);
}
void rek(int tren) {
if (tren == 0) {
for (int i = 0; i < sus[0].size(); i ++) {
rek(sus[0][i]);
}
}
for (int i = 0; i < sus[tren].size(); i ++) {
rek(sus[tren][i]);
p[tren] = p[tren]|p[sus[tren][i]];
}
}
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 < 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;*/
}
}
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;
}
return 0;
}
Compilation message
plahte.cpp: In function 'void rek(int)':
plahte.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sus[0].size(); i ++) {
~~^~~~~~~~~~~~~~~
plahte.cpp:83: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:145: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 |
Incorrect |
121 ms |
20476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
21228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
246 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
394 ms |
28928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
407 ms |
29124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
