#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<algorithm>
using namespace std;
vector <pair<pair<int,int>,pair<int,int> > > v,v4;
vector <int> v2,v3[80005];
set <int> t[525005],p[525005];
//vector <pair<int,int> > v1[160005];
vector <int> v5;
int off=1,parent[160005],cnt1[80005];
map <pair<int,int>,int> m1;
map <int,vector<pair<int,int> > > v1;
set <int> dfs(int x) {
//cout << x << "\n";
set <int> ret,s;
if(v[x].second.first==-1) {
ret.insert(m1[v[x].first]);
return ret;
}
for(int i=0;i<v3[x].size();i++) {
s=dfs(v3[x][i]);
if(ret.size()<s.size()) swap(ret,s);
for(set <int>::iterator it=s.begin();it!=s.end();it++) {
ret.insert(*it);
}
}
cnt1[x]=ret.size();
return ret;
}
void send(int x) {
if(p[x].size()==0) return;
for(set <int>::iterator it=p[x].begin();it!=p[x].end();it++) {
if((*it)>0) t[x].insert((*it));
else t[x].erase(-(*it));
}
if(x<off) {
for(set <int>::iterator it=p[x].begin();it!=p[x].end();it++) {
p[x*2].insert((*it));
p[x*2+1].insert((*it));
}
}
p[x].clear();
}
void update(int x,int lo,int hi,int l,int r,int v) {
if(lo>r or hi<l) return;
if(lo>=l && hi<=r) {
p[x].insert(v);
send(x);
return;
}
update(x*2,lo,(lo+hi)/2,l,r,v);
update(x*2+1,(lo+hi)/2+1,hi,l,r,v);
}
int query(int x,int lo,int hi,int l,int r) {
send(x);
if(lo>r or hi<l) return -1;
if(lo>=l && hi<=r) {
if(!t[x].empty()) {
set <int>::iterator it=t[x].end();
it--;
return (*it);
}
return -1;
}
return max(query(x*2,lo,(lo+hi)/2,l,r),query(x*2+1,(lo+hi)/2+1,hi,l,r));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,ind=0,cnt=0;
cin >> n >> m;
for(int i=0;i<n;i++) {
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
v2.push_back(x1);
v2.push_back(x2);
v2.push_back(y1);
v2.push_back(y2);
v.push_back(make_pair(make_pair(x1,y1),make_pair(x2,y2)));
}
for(int i=0;i<m;i++) {
int x,y,c;
cin >> x >> y >> c;
m1[make_pair(x,y)]=c;
v2.push_back(x);
v2.push_back(y);
v.push_back(make_pair(make_pair(x,y),make_pair(-1,-1)));
}
while(off<2*n+m) off*=2;
sort(v2.begin(),v2.end());
v2.erase(unique(v2.begin(),v2.end()),v2.end());
for(int i=0;i<n+m;i++) {
int a=0;
if(v[i].second.first==-1) a=m1[v[i].first];
v[i].first.first=lower_bound(v2.begin(),v2.end(),v[i].first.first)-v2.begin()+1;
v[i].first.second=lower_bound(v2.begin(),v2.end(),v[i].first.second)-v2.begin()+1;
if(a) m1[v[i].first]=a;
if(v[i].second.first!=-1) {
v[i].second.first=lower_bound(v2.begin(),v2.end(),v[i].second.first)-v2.begin()+1;
v1[v[i].second.first+1].push_back(make_pair(v[i].first.second,v[i].second.second));
}
if(v[i].second.second!=-1) v[i].second.second=lower_bound(v2.begin(),v2.end(),v[i].second.second)-v2.begin()+1;
}
v4=v;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
/*cout << "\n";
for(int i=0;i<v.size();i++) {
cout << v[i].first.first << " " << v[i].first.second << " " << v[i].second.first << " " << v[i].second.second << "\n";
}
cout << "abc\n";*/
for(int i=1;i<=v2.size();i++) {
//cout << int(t[10].size()) << "\n";
for(int j=0;j<v1[i].size();j++) {
update(1,0,off-1,v1[i][j].first,v1[i][j].second,-1);
}
v5.clear();
//cout << "def\n";
while(ind<v.size() && v[ind].first.first==i) {
//cout << int(t[10].size()) << "\n";
if(v[ind].second.first==-1) {
v5.push_back(ind);
/*parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].first.second);
v3[query(1,0,off-1,v[ind].first.second,v[ind].first.second)-1].push_back(ind);*/
}
else {
//if(ind==5) cout << v[ind].first.second << " " << v[ind].second.second << "\n";
parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].second.second);
if(parent[ind]>0) v3[parent[ind]-1].push_back(ind);
//cout << int(t[10].size()) << "\n";
update(1,0,off-1,v[ind].first.second,v[ind].second.second,ind+1);
}
ind+=1;
}
for(int j=0;j<v5.size();j++) {
int ind1=v5[j];
parent[ind1]=query(1,0,off-1,v[ind1].first.second,v[ind1].first.second);
if(parent[ind1]>0) v3[parent[ind1]-1].push_back(ind1);
}
}
/*for(int i=0;i<v.size();i++) {
cout << parent[i] << "\n";
}
cout << "\n";*/
for(int i=0;i<v.size();i++) {
if(parent[i]==-1) dfs(i);
}
for(int i=0;i<n;i++) {
cout << cnt1[int(lower_bound(v.begin(),v.end(),v4[i])-v.begin())] << "\n";
//cout << "abc\n";
}
//assert(0);
//cout << "123\n";
/*for(int i=0;i<v.size();i++) {
cout << parent[i] << " ";
}*/
return 0;
}
Compilation message
plahte.cpp: In function 'std::set<int> dfs(int)':
plahte.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v3[x].size();i++) {
~^~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=v2.size();i++) {
~^~~~~~~~~~~
plahte.cpp:119:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v1[i].size();j++) {
~^~~~~~~~~~~~~
plahte.cpp:124:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<v.size() && v[ind].first.first==i) {
~~~^~~~~~~~~
plahte.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v5.size();j++) {
~^~~~~~~~~~
plahte.cpp:150:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++) {
~^~~~~~~~~
plahte.cpp:75:16: warning: unused variable 'cnt' [-Wunused-variable]
int n,m,ind=0,cnt=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1756 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1892 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2015 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2112 ms |
503924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2114 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
